Bug 661900 - LRU-SP not fully implemented in memory cache; r=michal
authorGeoff Brown <gbrown@mozilla.com>
Thu, 08 Sep 2011 14:00:24 +0200
changeset 76726 d469840a370f6ba0aea87b7dedefefab3f325f59
parent 76725 120aedf2c84f82277b5acd6d66efd24c5afdd66e
child 76727 9943ca23ec8a552704091608067c911ec32ae701
push id3
push userfelipc@gmail.com
push dateFri, 30 Sep 2011 20:09:13 +0000
reviewersmichal
bugs661900
milestone9.0a1
Bug 661900 - LRU-SP not fully implemented in memory cache; r=michal
netwerk/cache/nsMemoryCacheDevice.cpp
--- a/netwerk/cache/nsMemoryCacheDevice.cpp
+++ b/netwerk/cache/nsMemoryCacheDevice.cpp
@@ -44,17 +44,17 @@
 #include "nsCacheService.h"
 #include "nsICacheService.h"
 #include "nsIStorageStream.h"
 #include "nsICacheVisitor.h"
 #include "nsCRT.h"
 #include "nsCache.h"
 #include "nsReadableUtils.h"
 
-// The memory cache implements a variation of the "LRU-SP" caching algorithm
+// The memory cache implements the "LRU-SP" caching algorithm
 // described in "LRU-SP: A Size-Adjusted and Popularity-Aware LRU Replacement
 // Algorithm for Web Caching" by Kai Cheng and Yahiko Kambayashi.
 
 // We keep kQueueCount LRU queues, which should be about ceil(log2(mHardLimit))
 // The queues hold exponentially increasing ranges of floor(log2((size/nref)))
 // values for entries.
 // Entries larger than 2^(kQueueCount-1) go in the last queue.
 // Entries with no expiration go in the first queue.
@@ -374,41 +374,59 @@ nsMemoryCacheDevice::EvictEntry(nsCacheE
     
     if (deleteEntry)  delete entry;
 }
 
 
 void
 nsMemoryCacheDevice::EvictEntriesIfNecessary(void)
 {
-    nsCacheEntry * entry, * next;
-
+    nsCacheEntry * entry;
+    nsCacheEntry * maxEntry;
     CACHE_LOG_DEBUG(("EvictEntriesIfNecessary.  mTotalSize: %d, mHardLimit: %d,"
                      "mInactiveSize: %d, mSoftLimit: %d\n",
                      mTotalSize, mHardLimit, mInactiveSize, mSoftLimit));
     
     if ((mTotalSize < mHardLimit) && (mInactiveSize < mSoftLimit))
         return;
 
-    for (int i = kQueueCount - 1; i >= 0; --i) {
-        entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
-        while (entry != &mEvictionList[i]) {
-            if (entry->IsInUse()) {
+    PRUint32 now = SecondsFromPRTime(PR_Now());
+    PRUint64 entryCost = 0;
+    PRUint64 maxCost = 0;
+    do {
+        // LRU-SP eviction selection: Check the head of each segment (each
+        // eviction list, kept in LRU order) and select the maximal-cost
+        // entry for eviction. Cost is time-since-accessed * size / nref.
+        maxEntry = 0;
+        for (int i = kQueueCount - 1; i >= 0; --i) {
+            entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
+
+            // If the head of a list is in use, check the next available entry
+            while ((entry != &mEvictionList[i]) &&
+                   (entry->IsInUse())) {
                 entry = (nsCacheEntry *)PR_NEXT_LINK(entry);
-                continue;
             }
 
-            next = (nsCacheEntry *)PR_NEXT_LINK(entry);
-            EvictEntry(entry, DELETE_ENTRY);
-            entry = next;
-
-            if ((mTotalSize < mHardLimit) && (mInactiveSize < mSoftLimit))
-                return;
+            if (entry != &mEvictionList[i]) {
+                entryCost = (PRUint64)
+                    (now - entry->LastFetched()) * entry->Size() / 
+                    PR_MAX(1, entry->FetchCount());
+                if (!maxEntry || (entryCost > maxCost)) {
+                    maxEntry = entry;
+                    maxCost = entryCost;
+                }
+            }
+        }
+        if (maxEntry) {
+            EvictEntry(maxEntry, DELETE_ENTRY);
+        } else {
+            break;
         }
     }
+    while ((mTotalSize >= mHardLimit) || (mInactiveSize >= mSoftLimit));
 }
 
 
 int
 nsMemoryCacheDevice::EvictionList(nsCacheEntry * entry, PRInt32  deltaSize)
 {
     // favor items which never expire by putting them in the lowest-index queue
     if (entry->ExpirationTime() == nsICache::NO_EXPIRATION_TIME)