Bug 646641 - Part 2: Update SHistory so it understands that SHEntries may share content viewers. r=smaug
authorJustin Lebar <justin.lebar@gmail.com>
Fri, 13 May 2011 15:42:36 -0400
changeset 73668 cfea4859f45809693f6d00080ba427c5750c191d
parent 73667 883e581e0849aee53a3e7ed0b6a1a371e72ec856
child 73669 e0aab5011b705bc41e1307590c51320d5380cfe4
child 73677 eaf57c6dab7ff335ccd3d2699b23e4a95c5a0a78
push id909
push userjlebar@mozilla.com
push dateTue, 02 Aug 2011 14:05:39 +0000
treeherdermozilla-inbound@cfea4859f458 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssmaug
bugs646641
milestone8.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 646641 - Part 2: Update SHistory so it understands that SHEntries may share content viewers. r=smaug
docshell/base/nsDocShell.cpp
docshell/shistory/public/nsISHistoryInternal.idl
docshell/shistory/src/nsSHistory.cpp
docshell/shistory/src/nsSHistory.h
docshell/test/chrome/bug396519_window.xul
layout/base/nsDocumentViewer.cpp
mobile/app/mobile.js
modules/libpref/src/init/all.js
--- a/docshell/base/nsDocShell.cpp
+++ b/docshell/base/nsDocShell.cpp
@@ -9644,19 +9644,19 @@ nsDocShell::AddState(nsIVariant *aData, 
     // 5. If aReplace is false (i.e. we're doing a pushState instead of a
     //    replaceState), notify bfcache that we've navigated to a new page.
     // 6. If the third argument is present, set the document's current address
     //    to the absolute URL found in step 2.
     //
     // It's important that this function not run arbitrary scripts after step 1
     // and before completing step 5.  For example, if a script called
     // history.back() before we completed step 5, bfcache might destroy an
-    // active content viewer.  Since EvictContentViewers at the end of step 5
-    // might run script, we can't just put a script blocker around the critical
-    // section.
+    // active content viewer.  Since EvictOutOfRangeContentViewers at the end of
+    // step 5 might run script, we can't just put a script blocker around the
+    // critical section.
     //
     // Note that we completely ignore the aTitle parameter.
 
     nsresult rv;
 
     nsCOMPtr<nsIDocument> document = do_GetInterface(GetAsSupports(this));
     NS_ENSURE_TRUE(document, NS_ERROR_FAILURE);
 
@@ -9874,17 +9874,17 @@ nsDocShell::AddState(nsIVariant *aData, 
 
         nsCOMPtr<nsISHistoryInternal> internalSH =
             do_QueryInterface(rootSH);
         NS_ENSURE_TRUE(internalSH, NS_ERROR_UNEXPECTED);
 
         PRInt32 curIndex = -1;
         rv = rootSH->GetIndex(&curIndex);
         if (NS_SUCCEEDED(rv) && curIndex > -1) {
-            internalSH->EvictContentViewers(curIndex - 1, curIndex);
+            internalSH->EvictOutOfRangeContentViewers(curIndex);
         }
     }
 
     // Step 6: If the document's URI changed, update document's URI and update
     // global history.
     //
     // We need to call FireOnLocationChange so that the browser's address bar
     // gets updated and the back button is enabled, but we only need to
--- a/docshell/shistory/public/nsISHistoryInternal.idl
+++ b/docshell/shistory/public/nsISHistoryInternal.idl
@@ -52,17 +52,17 @@ interface nsIDocShell;
 #define NS_SHISTORY_INTERNAL_CONTRACTID "@mozilla.org/browser/shistory-internal;1"
 
 template<class E, class A> class nsTArray;
 struct nsTArrayDefaultAllocator;
 %}
 
 [ref] native nsDocshellIDArray(nsTArray<PRUint64, nsTArrayDefaultAllocator>);
 
-[scriptable, uuid(AFE77866-8859-4492-B131-4C58167E1630)]
+[scriptable, uuid(e27cf38e-c19f-4294-bd31-d7e0916e7fa2)]
 interface nsISHistoryInternal: nsISupports
 {
   /**
    * Add a new Entry to the History List
    * @param aEntry - The entry to add
    * @param aPersist - If true this specifies that the entry should persist
    * in the list.  If false, this means that when new entries are added
    * this element will not appear in the session history list.
@@ -91,24 +91,29 @@ interface nsISHistoryInternal: nsISuppor
    */
    void replaceEntry(in long aIndex, in nsISHEntry aReplaceEntry);
 
   /** 
    * Get handle to the history listener
    */
    readonly attribute nsISHistoryListener listener;
 
-  /**
-   * Evict content viewers until the number of content viewers per tab
-   * is no more than gHistoryMaxViewers.  Also, count
-   * total number of content viewers globally and evict one if we are over
-   * our total max.  This is always called in Show(), after we destroy
-   * the previous viewer.
-   */
-   void evictContentViewers(in long previousIndex, in long index);
+   /**
+    * Evict content viewers which don't lie in the "safe" range around aIndex.
+    * In practice, this should leave us with no more than gHistoryMaxViewers
+    * viewers associated with this SHistory object.
+    *
+    * Also make sure that the total number of content viewers in all windows is
+    * not greater than our global max; if it is, evict viewers as appropriate.
+    *
+    * @param aIndex - The index around which the "safe" range is centered.  In
+    *   general, if you just navigated the history, aIndex should be the index
+    *   history was navigated to.
+    */
+   void evictOutOfRangeContentViewers(in long aIndex);
    
    /**
     * Evict the content viewer associated with a bfcache entry
     * that has timed out.
     */
    void evictExpiredContentViewerForEntry(in nsIBFCacheEntry aEntry);
 
    /**
--- a/docshell/shistory/src/nsSHistory.cpp
+++ b/docshell/shistory/src/nsSHistory.cpp
@@ -67,44 +67,72 @@
 // For calculating max history entries and max cachable contentviewers
 #include "nspr.h"
 #include <math.h>  // for log()
 
 using namespace mozilla;
 
 #define PREF_SHISTORY_SIZE "browser.sessionhistory.max_entries"
 #define PREF_SHISTORY_MAX_TOTAL_VIEWERS "browser.sessionhistory.max_total_viewers"
-#define PREF_SHISTORY_OPTIMIZE_EVICTION "browser.sessionhistory.optimize_eviction"
 
 static const char* kObservedPrefs[] = {
   PREF_SHISTORY_SIZE,
   PREF_SHISTORY_MAX_TOTAL_VIEWERS,
-  PREF_SHISTORY_OPTIMIZE_EVICTION,
   nsnull
 };
 
 static PRInt32  gHistoryMaxSize = 50;
 // Max viewers allowed per SHistory objects
 static const PRInt32  gHistoryMaxViewers = 3;
 // List of all SHistory objects, used for content viewer cache eviction
 static PRCList gSHistoryList;
 // Max viewers allowed total, across all SHistory objects - negative default
 // means we will calculate how many viewers to cache based on total memory
 PRInt32 nsSHistory::sHistoryMaxTotalViewers = -1;
 
-// Whether we should optimize the search for which entry to evict,
-// by evicting older entries first. See entryLastTouched in
-// nsSHistory::EvictGlobalContentViewer().
-// NB: After 4.0, we should remove this option and the corresponding
-//     pref - optimization should always be used
-static PRBool gOptimizeEviction = PR_FALSE;
 // A counter that is used to be able to know the order in which
 // entries were touched, so that we can evict older entries first.
 static PRUint32 gTouchCounter = 0;
 
+static PRLogModuleInfo* gLogModule = PR_LOG_DEFINE("nsSHistory");
+#define LOG(format) PR_LOG(gLogModule, PR_LOG_DEBUG, format)
+
+// This macro makes it easier to print a log message which includes a URI's
+// spec.  Example use:
+//
+//  nsIURI *uri = [...];
+//  LOG_SPEC(("The URI is %s.", _spec), uri);
+//
+#define LOG_SPEC(format, uri)                              \
+  PR_BEGIN_MACRO                                           \
+    if (PR_LOG_TEST(gLogModule, PR_LOG_DEBUG)) {           \
+      nsCAutoString _specStr(NS_LITERAL_CSTRING("(null)"));\
+      if (uri) {                                           \
+        uri->GetSpec(_specStr);                            \
+      }                                                    \
+      const char* _spec = _specStr.get();                  \
+      LOG(format);                                         \
+    }                                                      \
+  PR_END_MACRO
+
+// This macro makes it easy to log a message including an SHEntry's URI.
+// For example:
+//
+//  nsCOMPtr<nsISHEntry> shentry = [...];
+//  LOG_SHENTRY_SPEC(("shentry %p has uri %s.", shentry.get(), _spec), shentry);
+//
+#define LOG_SHENTRY_SPEC(format, shentry)                  \
+  PR_BEGIN_MACRO                                           \
+    if (PR_LOG_TEST(gLogModule, PR_LOG_DEBUG)) {           \
+      nsCOMPtr<nsIURI> uri;                                \
+      shentry->GetURI(getter_AddRefs(uri));                \
+      LOG_SPEC(format, uri);                               \
+    }                                                      \
+  PR_END_MACRO
+
 enum HistCmd{
   HIST_CMD_BACK,
   HIST_CMD_FORWARD,
   HIST_CMD_GOTOINDEX,
   HIST_CMD_RELOAD
 } ;
 
 //*****************************************************************************
@@ -129,25 +157,70 @@ static nsSHistoryObserver* gObserver = n
 NS_IMPL_ISUPPORTS1(nsSHistoryObserver, nsIObserver)
 
 NS_IMETHODIMP
 nsSHistoryObserver::Observe(nsISupports *aSubject, const char *aTopic,
                             const PRUnichar *aData)
 {
   if (!strcmp(aTopic, NS_PREFBRANCH_PREFCHANGE_TOPIC_ID)) {
     nsSHistory::UpdatePrefs();
-    nsSHistory::EvictGlobalContentViewer();
+    nsSHistory::GloballyEvictContentViewers();
   } else if (!strcmp(aTopic, NS_CACHESERVICE_EMPTYCACHE_TOPIC_ID) ||
              !strcmp(aTopic, "memory-pressure")) {
-    nsSHistory::EvictAllContentViewersGlobally();
+    nsSHistory::GloballyEvictAllContentViewers();
   }
 
   return NS_OK;
 }
 
+namespace {
+
+already_AddRefed<nsIContentViewer>
+GetContentViewerForTransaction(nsISHTransaction *aTrans)
+{
+  nsCOMPtr<nsISHEntry> entry;
+  aTrans->GetSHEntry(getter_AddRefs(entry));
+  if (!entry) {
+    return nsnull;
+  }
+
+  nsCOMPtr<nsISHEntry> ownerEntry;
+  nsCOMPtr<nsIContentViewer> viewer;
+  entry->GetAnyContentViewer(getter_AddRefs(ownerEntry),
+                             getter_AddRefs(viewer));
+  return viewer.forget();
+}
+
+void
+EvictContentViewerForTransaction(nsISHTransaction *aTrans)
+{
+  nsCOMPtr<nsISHEntry> entry;
+  aTrans->GetSHEntry(getter_AddRefs(entry));
+  nsCOMPtr<nsIContentViewer> viewer;
+  nsCOMPtr<nsISHEntry> ownerEntry;
+  entry->GetAnyContentViewer(getter_AddRefs(ownerEntry),
+                             getter_AddRefs(viewer));
+  if (viewer) {
+    NS_ASSERTION(ownerEntry,
+                 "Content viewer exists but its SHEntry is null");
+
+    LOG_SHENTRY_SPEC(("Evicting content viewer 0x%p for "
+                      "owning SHEntry 0x%p at %s.",
+                      viewer.get(), ownerEntry.get(), _spec), ownerEntry);
+
+    // Drop the presentation state before destroying the viewer, so that
+    // document teardown is able to correctly persist the state.
+    ownerEntry->SetContentViewer(nsnull);
+    ownerEntry->SyncPresentationState();
+    viewer->Destroy();
+  }
+}
+
+} // anonymous namespace
+
 //*****************************************************************************
 //***    nsSHistory: Object Management
 //*****************************************************************************
 
 nsSHistory::nsSHistory() : mListRoot(nsnull), mIndex(-1), mLength(0), mRequestedIndex(-1)
 {
   // Add this new SHistory object to the list
   PR_APPEND_LINK(this, &gSHistoryList);
@@ -235,17 +308,16 @@ nsSHistory::CalcMaxTotalViewers()
 
 // static
 void
 nsSHistory::UpdatePrefs()
 {
   Preferences::GetInt(PREF_SHISTORY_SIZE, &gHistoryMaxSize);
   Preferences::GetInt(PREF_SHISTORY_MAX_TOTAL_VIEWERS,
                       &sHistoryMaxTotalViewers);
-  Preferences::GetBool(PREF_SHISTORY_OPTIMIZE_EVICTION, &gOptimizeEviction);
   // If the pref is negative, that means we calculate how many viewers
   // we think we should cache, based on total memory
   if (sHistoryMaxTotalViewers < 0) {
     sHistoryMaxTotalViewers = CalcMaxTotalViewers();
   }
 }
 
 // static
@@ -684,31 +756,38 @@ nsSHistory::GetListener(nsISHistoryListe
   NS_ENSURE_ARG_POINTER(aListener);
   if (mListener) 
     CallQueryReferent(mListener.get(),  aListener);
   // Don't addref aListener. It is a weak pointer.
   return NS_OK;
 }
 
 NS_IMETHODIMP
-nsSHistory::EvictContentViewers(PRInt32 aPreviousIndex, PRInt32 aIndex)
+nsSHistory::EvictOutOfRangeContentViewers(PRInt32 aIndex)
 {
   // Check our per SHistory object limit in the currently navigated SHistory
-  EvictWindowContentViewers(aPreviousIndex, aIndex);
+  EvictOutOfRangeWindowContentViewers(aIndex);
   // Check our total limit across all SHistory objects
-  EvictGlobalContentViewer();
+  GloballyEvictContentViewers();
   return NS_OK;
 }
 
 NS_IMETHODIMP
 nsSHistory::EvictAllContentViewers()
 {
   // XXXbz we don't actually do a good job of evicting things as we should, so
   // we might have viewers quite far from mIndex.  So just evict everything.
-  EvictContentViewersInRange(0, mLength);
+  nsCOMPtr<nsISHTransaction> trans = mListRoot;
+  while (trans) {
+    EvictContentViewerForTransaction(trans);
+
+    nsISHTransaction *temp = trans;
+    temp->GetNext(getter_AddRefs(trans));
+  }
+
   return NS_OK;
 }
 
 
 
 //*****************************************************************************
 //    nsSHistory: nsIWebNavigation
 //*****************************************************************************
@@ -842,248 +921,238 @@ nsSHistory::ReloadCurrentEntry()
   }
   if (!canNavigate)
     return NS_OK;
 
   return LoadEntry(mIndex, nsIDocShellLoadInfo::loadHistory, HIST_CMD_RELOAD);
 }
 
 void
-nsSHistory::EvictWindowContentViewers(PRInt32 aFromIndex, PRInt32 aToIndex)
+nsSHistory::EvictOutOfRangeWindowContentViewers(PRInt32 aIndex)
 {
-  // To enforce the per SHistory object limit on cached content viewers, we
-  // need to release all of the content viewers that are no longer in the
-  // "window" that now ends/begins at aToIndex.  Existing content viewers
-  // should be in the window from
-  // aFromIndex - gHistoryMaxViewers to aFromIndex + gHistoryMaxViewers
+  // XXX rename method to EvictContentViewersExceptAroundIndex, or something.
+
+  // We need to release all content viewers that are no longer in the range
+  //
+  //  aIndex - gHistoryMaxViewers to aIndex + gHistoryMaxViewers
+  //
+  // to ensure that this SHistory object isn't responsible for more than
+  // gHistoryMaxViewers content viewers.  But our job is complicated by the
+  // fact that two transactions which are related by either hash navigations or
+  // history.pushState will have the same content viewer.
+  //
+  // To illustrate the issue, suppose gHistoryMaxViewers = 3 and we have four
+  // linked transactions in our history.  Suppose we then add a new content
+  // viewer and call into this function.  So the history looks like:
+  //
+  //   A A A A B
+  //     +     *
   //
-  // We make the assumption that entries outside this range have no viewers so
-  // that we don't have to walk the whole entire session history checking for
-  // content viewers.
+  // where the letters are content viewers and + and * denote the beginning and
+  // end of the range aIndex +/- gHistoryMaxViewers.
+  //
+  // Although one copy of the content viewer A exists outside the range, we
+  // don't want to evict A, because it has other copies in range!
+  //
+  // We therefore adjust our eviction strategy to read:
+  //
+  //   Evict each content viewer outside the range aIndex -/+
+  //   gHistoryMaxViewers, unless that content viewer also appears within the
+  //   range.
+  //
+  // (Note that it's entirely legal to have two copies of one content viewer
+  // separated by a different content viewer -- call pushState twice, go back
+  // once, and refresh -- so we can't rely on identical viewers only appearing
+  // adjacent to one another.)
 
-  // This can happen on the first load of a page in a particular window
-  if (aFromIndex < 0 || aToIndex < 0) {
+  if (aIndex < 0) {
     return;
   }
-  NS_ASSERTION(aFromIndex < mLength, "aFromIndex is out of range");
-  NS_ASSERTION(aToIndex < mLength, "aToIndex is out of range");
-  if (aFromIndex >= mLength || aToIndex >= mLength) {
+  NS_ASSERTION(aIndex < mLength, "aIndex is out of range");
+  if (aIndex >= mLength) {
     return;
   }
 
-  // These indices give the range of SHEntries whose content viewers will be
-  // evicted
-  PRInt32 startIndex, endIndex;
-  if (aToIndex > aFromIndex) { // going forward
-    endIndex = aToIndex - gHistoryMaxViewers;
-    if (endIndex <= 0) {
-      return;
-    }
-    startIndex = NS_MAX(0, aFromIndex - gHistoryMaxViewers);
-  } else { // going backward
-    startIndex = aToIndex + gHistoryMaxViewers + 1;
-    if (startIndex >= mLength) {
-      return;
-    }
-    endIndex = NS_MIN(mLength, aFromIndex + gHistoryMaxViewers + 1);
-  }
+  // Calculate the range that's safe from eviction.
+  PRInt32 startSafeIndex = PR_MAX(0, aIndex - gHistoryMaxViewers);
+  PRInt32 endSafeIndex = PR_MIN(mLength, aIndex + gHistoryMaxViewers);
+
+  LOG(("EvictOutOfRangeWindowContentViewers(index=%d), "
+       "mLength=%d. Safe range [%d, %d]",
+       aIndex, mLength, startSafeIndex, endSafeIndex)); 
 
-#ifdef DEBUG
+  // The content viewers in range aIndex -/+ gHistoryMaxViewers will not be
+  // evicted.  Collect a set of them so we don't accidentally evict one of them
+  // if it appears outside this range.
+  nsCOMArray<nsIContentViewer> safeViewers;
   nsCOMPtr<nsISHTransaction> trans;
-  GetTransactionAtIndex(0, getter_AddRefs(trans));
-
-  // Walk the full session history and check that entries outside the window
-  // around aFromIndex have no content viewers
-  for (PRInt32 i = 0; trans && i < mLength; ++i) {
-    if (i < aFromIndex - gHistoryMaxViewers || 
-        i > aFromIndex + gHistoryMaxViewers) {
-      nsCOMPtr<nsISHEntry> entry;
-      trans->GetSHEntry(getter_AddRefs(entry));
-      nsCOMPtr<nsIContentViewer> viewer;
-      nsCOMPtr<nsISHEntry> ownerEntry;
-      entry->GetAnyContentViewer(getter_AddRefs(ownerEntry),
-                                 getter_AddRefs(viewer));
-      NS_WARN_IF_FALSE(!viewer,
-                       "ContentViewer exists outside gHistoryMaxViewer range");
-    }
-
+  GetTransactionAtIndex(startSafeIndex, getter_AddRefs(trans));
+  for (PRUint32 i = startSafeIndex; trans && i <= endSafeIndex; i++) {
+    nsCOMPtr<nsIContentViewer> viewer = GetContentViewerForTransaction(trans);
+    safeViewers.AppendObject(viewer);
     nsISHTransaction *temp = trans;
     temp->GetNext(getter_AddRefs(trans));
   }
-#endif
 
-  EvictContentViewersInRange(startIndex, endIndex);
-}
-
-void
-nsSHistory::EvictContentViewersInRange(PRInt32 aStart, PRInt32 aEnd)
-{
-  nsCOMPtr<nsISHTransaction> trans;
-  GetTransactionAtIndex(aStart, getter_AddRefs(trans));
-
-  for (PRInt32 i = aStart; trans && i < aEnd; ++i) {
-    nsCOMPtr<nsISHEntry> entry;
-    trans->GetSHEntry(getter_AddRefs(entry));
-    nsCOMPtr<nsIContentViewer> viewer;
-    nsCOMPtr<nsISHEntry> ownerEntry;
-    entry->GetAnyContentViewer(getter_AddRefs(ownerEntry),
-                               getter_AddRefs(viewer));
-    if (viewer) {
-      NS_ASSERTION(ownerEntry,
-                   "ContentViewer exists but its SHEntry is null");
-#ifdef DEBUG_PAGE_CACHE
-      nsCOMPtr<nsIURI> uri;
-      ownerEntry->GetURI(getter_AddRefs(uri));
-      nsCAutoString spec;
-      if (uri)
-        uri->GetSpec(spec);
-
-      printf("per SHistory limit: evicting content viewer: %s\n", spec.get());
-#endif
-
-      // Drop the presentation state before destroying the viewer, so that
-      // document teardown is able to correctly persist the state.
-      ownerEntry->SetContentViewer(nsnull);
-      ownerEntry->SyncPresentationState();
-      viewer->Destroy();
+  // Walk the SHistory list and evict any content viewers that aren't safe.
+  GetTransactionAtIndex(0, getter_AddRefs(trans));
+  while (trans) {
+    nsCOMPtr<nsIContentViewer> viewer = GetContentViewerForTransaction(trans);
+    if (safeViewers.IndexOf(viewer) == -1) {
+      EvictContentViewerForTransaction(trans);
     }
 
     nsISHTransaction *temp = trans;
     temp->GetNext(getter_AddRefs(trans));
   }
 }
 
-// static
-void
-nsSHistory::EvictGlobalContentViewer()
+namespace {
+
+class TransactionAndDistance
 {
-  // true until the total number of content viewers is <= total max
-  // The usual case is that we only need to evict one content viewer.
-  // However, if somebody resets the pref value, we might occasionally
-  // need to evict more than one.
-  PRBool shouldTryEviction = PR_TRUE;
-  while (shouldTryEviction) {
-    // Walk through our list of SHistory objects, looking for content
-    // viewers in the possible active window of all of the SHEntry objects.
-    // Keep track of the SHEntry object that has a ContentViewer and is
-    // farthest from the current focus in any SHistory object.  The
-    // ContentViewer associated with that SHEntry will be evicted
-    PRInt32 distanceFromFocus = 0;
-    PRUint32 candidateLastTouched = 0;
-    nsCOMPtr<nsISHEntry> evictFromSHE;
-    nsCOMPtr<nsIContentViewer> evictViewer;
-    PRInt32 totalContentViewers = 0;
-    nsSHistory* shist = static_cast<nsSHistory*>
-                                   (PR_LIST_HEAD(&gSHistoryList));
-    while (shist != &gSHistoryList) {
-      // Calculate the window of SHEntries that could possibly have a content
-      // viewer.  There could be up to gHistoryMaxViewers content viewers,
-      // but we don't know whether they are before or after the mIndex position
-      // in the SHEntry list.  Just check both sides, to be safe.
-      PRInt32 startIndex = NS_MAX(0, shist->mIndex - gHistoryMaxViewers);
-      PRInt32 endIndex = NS_MIN(shist->mLength - 1,
-                                shist->mIndex + gHistoryMaxViewers);
-      nsCOMPtr<nsISHTransaction> trans;
-      shist->GetTransactionAtIndex(startIndex, getter_AddRefs(trans));
+public:
+  TransactionAndDistance(nsISHTransaction *aTrans, PRUint32 aDist)
+    : mTransaction(aTrans)
+    , mDistance(aDist)
+  {
+    mViewer = GetContentViewerForTransaction(aTrans);
+    NS_ASSERTION(mViewer, "Transaction should have a content viewer");
+
+    nsCOMPtr<nsISHEntry> shentry;
+    mTransaction->GetSHEntry(getter_AddRefs(shentry));
+
+    nsCOMPtr<nsISHEntryInternal> shentryInternal = do_QueryInterface(shentry);
+    if (shentryInternal) {
+      shentryInternal->GetLastTouched(&mLastTouched);
+    } else {
+      NS_WARNING("Can't cast to nsISHEntryInternal?");
+      mLastTouched = 0;
+    }
+  }
+
+  bool operator<(const TransactionAndDistance &aOther) const
+  {
+    // Compare distances first, and fall back to last-accessed times.
+    if (aOther.mDistance != this->mDistance) {
+      return this->mDistance < aOther.mDistance;
+    }
+
+    return this->mLastTouched < aOther.mLastTouched;
+  }
+
+  bool operator==(const TransactionAndDistance &aOther) const
+  {
+    // This is a little silly; we need == so the default comaprator can be
+    // instantiated, but this function is never actually called when we sort
+    // the list of TransactionAndDistance objects.
+    return aOther.mDistance == this->mDistance &&
+           aOther.mLastTouched == this->mLastTouched;
+  }
+
+  nsCOMPtr<nsISHTransaction> mTransaction;
+  nsCOMPtr<nsIContentViewer> mViewer;
+  PRUint32 mLastTouched;
+  PRInt32 mDistance;
+};
+
+} // anonymous namespace
 
-      for (PRInt32 i = startIndex; trans && i <= endIndex; ++i) {
-        nsCOMPtr<nsISHEntry> entry;
-        trans->GetSHEntry(getter_AddRefs(entry));
-        nsCOMPtr<nsIContentViewer> viewer;
-        nsCOMPtr<nsISHEntry> ownerEntry;
-        entry->GetAnyContentViewer(getter_AddRefs(ownerEntry),
-                                   getter_AddRefs(viewer));
+//static
+void
+nsSHistory::GloballyEvictContentViewers()
+{
+  // First, collect from each SHistory object the transactions which have a
+  // cached content viewer.  Associate with each transaction its distance from
+  // its SHistory's current index.
+
+  nsTArray<TransactionAndDistance> transactions;
+
+  nsSHistory *shist = static_cast<nsSHistory*>(PR_LIST_HEAD(&gSHistoryList));
+  while (shist != &gSHistoryList) {
+
+    // Maintain a list of the transactions which have viewers and belong to
+    // this particular shist object.  We'll add this list to the global list,
+    // |transactions|, eventually.
+    nsTArray<TransactionAndDistance> shTransactions;
 
-        PRUint32 entryLastTouched = 0;
-        if (gOptimizeEviction) {
-          nsCOMPtr<nsISHEntryInternal> entryInternal = do_QueryInterface(entry);
-          if (entryInternal) {
-            // Find when this entry was last activated
-            entryInternal->GetLastTouched(&entryLastTouched);
+    // Content viewers are likely to exist only within shist->mIndex -/+
+    // gHistoryMaxViewers, so only search within that range.
+    //
+    // A content viewer might exist outside that range due to either:
+    //
+    //   * history.pushState or hash navigations, in which case a copy of the
+    //     content viewer should exist within the range, or
+    //
+    //   * bugs which cause us not to call nsSHistory::EvictContentViewers()
+    //     often enough.  Once we do call EvictContentViewers() for the
+    //     SHistory object in question, we'll do a full search of its history
+    //     and evict the out-of-range content viewers, so we don't bother here.
+    //
+    PRInt32 startIndex = NS_MAX(0, shist->mIndex - gHistoryMaxViewers);
+    PRInt32 endIndex = NS_MIN(shist->mLength - 1,
+                              shist->mIndex + gHistoryMaxViewers);
+    nsCOMPtr<nsISHTransaction> trans;
+    shist->GetTransactionAtIndex(startIndex, getter_AddRefs(trans));
+    for (PRInt32 i = startIndex; trans && i <= endIndex; i++) {
+      nsCOMPtr<nsIContentViewer> contentViewer =
+        GetContentViewerForTransaction(trans);
+
+      if (contentViewer) {
+        // Because one content viewer might belong to multiple SHEntries, we
+        // have to search through shTransactions to see if we already know
+        // about this content viewer.  If we find the viewer, update its
+        // distance from the SHistory's index and continue.
+        PRBool found = PR_FALSE;
+        for (PRUint32 j = 0; j < shTransactions.Length(); j++) {
+          TransactionAndDistance &container = shTransactions[j];
+          if (container.mViewer == contentViewer) {
+            container.mDistance = PR_MIN(container.mDistance,
+                                         PR_ABS(i - shist->mIndex));
+            found = PR_TRUE;
+            break;
           }
         }
 
-#ifdef DEBUG_PAGE_CACHE
-        nsCOMPtr<nsIURI> uri;
-        if (ownerEntry) {
-          ownerEntry->GetURI(getter_AddRefs(uri));
-        } else {
-          entry->GetURI(getter_AddRefs(uri));
-        }
-        nsCAutoString spec;
-        if (uri) {
-          uri->GetSpec(spec);
-          printf("Considering for eviction: %s\n", spec.get());
+        // If we didn't find a TransactionAndDistance for this content viewer, make a new
+        // one.
+        if (!found) {
+          TransactionAndDistance container(trans, PR_ABS(i - shist->mIndex));
+          shTransactions.AppendElement(container);
         }
-#endif
-        
-        // This SHEntry has a ContentViewer, so check how far away it is from
-        // the currently used SHEntry within this SHistory object
-        if (viewer) {
-          PRInt32 distance = NS_ABS(shist->mIndex - i);
-          
-#ifdef DEBUG_PAGE_CACHE
-          printf("Has a cached content viewer: %s\n", spec.get());
-          printf("mIndex: %d i: %d\n", shist->mIndex, i);
-#endif
-          totalContentViewers++;
+      }
 
-          // If this entry is further away from focus than any previously found
-          // or at the same distance but it is longer time since it was activated
-          // then take this entry as the new candiate for eviction
-          if (distance > distanceFromFocus || (distance == distanceFromFocus && candidateLastTouched > entryLastTouched)) {
-
-#ifdef DEBUG_PAGE_CACHE
-            printf("Choosing as new eviction candidate: %s\n", spec.get());
-#endif
-            candidateLastTouched = entryLastTouched;
-            distanceFromFocus = distance;
-            evictFromSHE = ownerEntry;
-            evictViewer = viewer;
-          }
-        }
-        nsISHTransaction* temp = trans;
-        temp->GetNext(getter_AddRefs(trans));
-      }
-      shist = static_cast<nsSHistory*>(PR_NEXT_LINK(shist));
+      nsISHTransaction *temp = trans;
+      temp->GetNext(getter_AddRefs(trans));
     }
 
-#ifdef DEBUG_PAGE_CACHE
-    printf("Distance from focus: %d\n", distanceFromFocus);
-    printf("Total max viewers: %d\n", sHistoryMaxTotalViewers);
-    printf("Total number of viewers: %d\n", totalContentViewers);
-#endif
+    // We've found all the transactions belonging to shist which have viewers.
+    // Add those transactions to our global list and move on.
+    transactions.AppendElements(shTransactions);
+    shist = static_cast<nsSHistory*>(PR_NEXT_LINK(shist));
+  }
 
-    if (totalContentViewers > sHistoryMaxTotalViewers && evictViewer) {
-#ifdef DEBUG_PAGE_CACHE
-      nsCOMPtr<nsIURI> uri;
-      evictFromSHE->GetURI(getter_AddRefs(uri));
-      nsCAutoString spec;
-      if (uri) {
-        uri->GetSpec(spec);
-        printf("Evicting content viewer: %s\n", spec.get());
-      }
-#endif
+  // We now have collected all cached content viewers.  First check that we
+  // have enough that we actually need to evict some.
+  if ((PRInt32)transactions.Length() <= sHistoryMaxTotalViewers) {
+    return;
+  }
 
-      // Drop the presentation state before destroying the viewer, so that
-      // document teardown is able to correctly persist the state.
-      evictFromSHE->SetContentViewer(nsnull);
-      evictFromSHE->SyncPresentationState();
-      evictViewer->Destroy();
+  // If we need to evict, sort our list of transactions and evict the largest
+  // ones.  (We could of course get better algorithmic complexity here by using
+  // a heap or something more clever.  But sHistoryMaxTotalViewers isn't large,
+  // so let's not worry about it.)
+  transactions.Sort();
 
-      // If we only needed to evict one content viewer, then we are done.
-      // Otherwise, continue evicting until we reach the max total limit.
-      if (totalContentViewers - sHistoryMaxTotalViewers == 1) {
-        shouldTryEviction = PR_FALSE;
-      }
-    } else {
-      // couldn't find a content viewer to evict, so we are done
-      shouldTryEviction = PR_FALSE;
-    }
-  }  // while shouldTryEviction
+  for (PRInt32 i = transactions.Length() - 1;
+       i >= sHistoryMaxTotalViewers; --i) {
+
+    EvictContentViewerForTransaction(transactions[i].mTransaction);
+
+  }
 }
 
 nsresult
 nsSHistory::EvictExpiredContentViewerForEntry(nsIBFCacheEntry *aEntry)
 {
   PRInt32 startIndex = NS_MAX(0, mIndex - gHistoryMaxViewers);
   PRInt32 endIndex = NS_MIN(mLength - 1,
                             mIndex + gHistoryMaxViewers);
@@ -1101,46 +1170,38 @@ nsSHistory::EvictExpiredContentViewerFor
     }
 
     nsISHTransaction *temp = trans;
     temp->GetNext(getter_AddRefs(trans));
   }
   if (i > endIndex)
     return NS_OK;
   
-  NS_ASSERTION(i != mIndex, "How did the current session entry expire?");
-  if (i == mIndex)
+  if (i == mIndex) {
+    NS_WARNING("How did the current SHEntry expire?");
     return NS_OK;
-  
-  // We evict content viewers for the expired entry and any other entries that
-  // we would have to go through the expired entry to get to (i.e. the entries
-  // that have the expired entry between them and the current entry). Those
-  // other entries should have timed out already, actually, but this is just
-  // to be on the safe side.
-  if (i < mIndex) {
-    EvictContentViewersInRange(startIndex, i + 1);
-  } else {
-    EvictContentViewersInRange(i, endIndex + 1);
   }
 
+  EvictContentViewerForTransaction(trans);
+
   return NS_OK;
 }
 
 // Evicts all content viewers in all history objects.  This is very
 // inefficient, because it requires a linear search through all SHistory
 // objects for each viewer to be evicted.  However, this method is called
 // infrequently -- only when the disk or memory cache is cleared.
 
 //static
 void
-nsSHistory::EvictAllContentViewersGlobally()
+nsSHistory::GloballyEvictAllContentViewers()
 {
   PRInt32 maxViewers = sHistoryMaxTotalViewers;
   sHistoryMaxTotalViewers = 0;
-  EvictGlobalContentViewer();
+  GloballyEvictContentViewers();
   sHistoryMaxTotalViewers = maxViewers;
 }
 
 void GetDynamicChildren(nsISHContainer* aContainer,
                         nsTArray<PRUint64>& aDocshellIDs,
                         PRBool aOnlyTopLevelDynamic)
 {
   PRInt32 count = 0;
--- a/docshell/shistory/src/nsSHistory.h
+++ b/docshell/shistory/src/nsSHistory.h
@@ -96,22 +96,21 @@ protected:
    nsresult InitiateLoad(nsISHEntry * aFrameEntry, nsIDocShell * aFrameDS, long aLoadType);
 
    NS_IMETHOD LoadEntry(PRInt32 aIndex, long aLoadType, PRUint32 histCmd);
 
 #ifdef DEBUG
    nsresult PrintHistory();
 #endif
 
-  // Evict the viewers at indices between aStartIndex and aEndIndex,
-  // including aStartIndex but not aEndIndex.
-  void EvictContentViewersInRange(PRInt32 aStartIndex, PRInt32 aEndIndex);
-  void EvictWindowContentViewers(PRInt32 aFromIndex, PRInt32 aToIndex);
-  static void EvictGlobalContentViewer();
-  static void EvictAllContentViewersGlobally();
+  // Evict content viewers in this window which don't lie in the "safe" range
+  // around aIndex.
+  void EvictOutOfRangeWindowContentViewers(PRInt32 aIndex);
+  static void GloballyEvictContentViewers();
+  static void GloballyEvictAllContentViewers();
 
   // Calculates a max number of total
   // content viewers to cache, based on amount of total memory
   static PRUint32 CalcMaxTotalViewers();
 
   void RemoveDynEntries(PRInt32 aOldIndex, PRInt32 aNewIndex);
 
   nsresult LoadNextPossibleEntry(PRInt32 aNewIndex, long aLoadType, PRUint32 aHistCmd);
--- a/docshell/test/chrome/bug396519_window.xul
+++ b/docshell/test/chrome/bug396519_window.xul
@@ -45,16 +45,19 @@
         height="600"
         onload="onLoad();"
         title="396519 test">
 
   <script type="application/javascript"><![CDATA[
 
     const LISTEN_EVENTS = ["pageshow"];
 
+    const Cc = Components.classes;
+    const Ci = Components.interfaces;
+
     var gBrowser;
     var gTestCount = 0;
     var gTestsIterator;
     var gExpected = [];
 
     function ok(condition, message) {
       window.opener.wrappedJSObject.SimpleTest.ok(condition, message);
     }
@@ -91,16 +94,33 @@
     function doTest() {
       var history = gBrowser.webNavigation.sessionHistory;
       if (history.count == gExpected.length) {
         for (var i=0; i<history.count; i++) {
           var shEntry = history.getEntryAtIndex(i,false).
                           QueryInterface(Components.interfaces.nsISHEntry);
           is(!!shEntry.contentViewer, gExpected[i], "content viewer "+i+", test "+gTestCount);
         }
+
+        // Make sure none of the SHEntries share bfcache entries with one
+        // another.
+        for (var i = 0; i < history.count; i++) {
+          for (var j = 0; j < history.count; j++) {
+            if (j == i)
+              continue;
+
+            let shentry1 = history.getEntryAtIndex(i, false)
+                                  .QueryInterface(Ci.nsISHEntry);
+            let shentry2 = history.getEntryAtIndex(j, false)
+                                  .QueryInterface(Ci.nsISHEntry);
+            ok(!shentry1.sharesDocumentWith(shentry2),
+               'Test ' + gTestCount + ': shentry[' + i + "] shouldn't " +
+               "share document with shentry[" + j + ']');
+          }
+        }
       }
       else {
         is(history.count, gExpected.length, "Wrong history length in test "+gTestCount);
       }
 
       setTimeout(nextTest, 0);
     }
 
--- a/layout/base/nsDocumentViewer.cpp
+++ b/layout/base/nsDocumentViewer.cpp
@@ -1975,17 +1975,17 @@ DocumentViewerImpl::Show(void)
         PRInt32 prevIndex,loadedIndex;
         nsCOMPtr<nsIDocShell> docShell = do_QueryInterface(treeItem);
         docShell->GetPreviousTransIndex(&prevIndex);
         docShell->GetLoadedTransIndex(&loadedIndex);
 #ifdef DEBUG_PAGE_CACHE
         printf("About to evict content viewers: prev=%d, loaded=%d\n",
                prevIndex, loadedIndex);
 #endif
-        historyInt->EvictContentViewers(prevIndex, loadedIndex);
+        historyInt->EvictOutOfRangeContentViewers(loadedIndex);
       }
     }
   }
 
   if (mWindow) {
     // When attached to a top level xul window, we do not need to call
     // Show on the widget. Underlying window management code handles
     // this when the window is initialized.
--- a/mobile/app/mobile.js
+++ b/mobile/app/mobile.js
@@ -125,17 +125,16 @@ pref("network.buffer.cache.size",  16384
 pref("browser.display.history.maxresults", 100);
 
 /* How many times should have passed before the remote tabs list is refreshed */
 pref("browser.display.remotetabs.timeout", 10);
 
 /* session history */
 pref("browser.sessionhistory.max_total_viewers", 1);
 pref("browser.sessionhistory.max_entries", 50);
-pref("browser.sessionhistory.optimize_eviction", true);
 
 /* session store */
 pref("browser.sessionstore.resume_session_once", false);
 pref("browser.sessionstore.resume_from_crash", true);
 pref("browser.sessionstore.resume_from_crash_timeout", 60); // minutes
 pref("browser.sessionstore.interval", 10000); // milliseconds
 pref("browser.sessionstore.max_tabs_undo", 1);
 
--- a/modules/libpref/src/init/all.js
+++ b/modules/libpref/src/init/all.js
@@ -104,18 +104,16 @@ pref("dom.workers.maxPerDomain", 20);
 
 // Whether window.performance is enabled
 pref("dom.enable_performance", true);
 
 // Fastback caching - if this pref is negative, then we calculate the number
 // of content viewers to cache based on the amount of available memory.
 pref("browser.sessionhistory.max_total_viewers", -1);
 
-pref("browser.sessionhistory.optimize_eviction", true);
-
 pref("ui.use_native_colors", true);
 pref("ui.click_hold_context_menus", false);
 pref("browser.display.use_document_fonts",  1);  // 0 = never, 1 = quick, 2 = always
 pref("browser.display.use_document_colors", true);
 pref("browser.display.use_system_colors",   false);
 pref("browser.display.foreground_color",    "#000000");
 pref("browser.display.background_color",    "#FFFFFF");
 pref("browser.display.force_inline_alttext", false); // true = force ALT text for missing images to be layed out inline