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 73700 cfea4859f45809693f6d00080ba427c5750c191d
parent 73699 883e581e0849aee53a3e7ed0b6a1a371e72ec856
child 73701 e0aab5011b705bc41e1307590c51320d5380cfe4
child 73709 eaf57c6dab7ff335ccd3d2699b23e4a95c5a0a78
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
reviewerssmaug
bugs646641
milestone8.0a1
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