Back to index

lightning-sunbird  0.9+nobinonly
nsMemoryCacheDevice.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  *
00003  * ***** BEGIN LICENSE BLOCK *****
00004  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00005  *
00006  * The contents of this file are subject to the Mozilla Public License Version
00007  * 1.1 (the "License"); you may not use this file except in compliance with
00008  * the License. You may obtain a copy of the License at
00009  * http://www.mozilla.org/MPL/
00010  *
00011  * Software distributed under the License is distributed on an "AS IS" basis,
00012  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00013  * for the specific language governing rights and limitations under the
00014  * License.
00015  *
00016  * The Original Code is nsMemoryCacheDevice.cpp, released
00017  * February 22, 2001.
00018  *
00019  * The Initial Developer of the Original Code is
00020  * Netscape Communications Corporation.
00021  * Portions created by the Initial Developer are Copyright (C) 2001
00022  * the Initial Developer. All Rights Reserved.
00023  *
00024  * Contributor(s):
00025  *   Gordon Sheridan, <gordon@netscape.com>
00026  *   Patrick C. Beard <beard@netscape.com>
00027  *   Brian Ryner <bryner@brianryner.com>
00028  *
00029  * Alternatively, the contents of this file may be used under the terms of
00030  * either the GNU General Public License Version 2 or later (the "GPL"), or
00031  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00032  * in which case the provisions of the GPL or the LGPL are applicable instead
00033  * of those above. If you wish to allow use of your version of this file only
00034  * under the terms of either the GPL or the LGPL, and not to allow others to
00035  * use your version of this file under the terms of the MPL, indicate your
00036  * decision by deleting the provisions above and replace them with the notice
00037  * and other provisions required by the GPL or the LGPL. If you do not delete
00038  * the provisions above, a recipient may use your version of this file under
00039  * the terms of any one of the MPL, the GPL or the LGPL.
00040  *
00041  * ***** END LICENSE BLOCK ***** */
00042 
00043 #include "nsMemoryCacheDevice.h"
00044 #include "nsCacheService.h"
00045 #include "nsICacheService.h"
00046 #include "nsIStorageStream.h"
00047 #include "nsICacheVisitor.h"
00048 #include "nsCRT.h"
00049 #include "nsCache.h"
00050 #include "nsReadableUtils.h"
00051 
00052 // The memory cache implements a variation of the "LRU-SP" caching algorithm
00053 // described in "LRU-SP: A Size-Adjusted and Popularity-Aware LRU Replacement
00054 // Algorithm for Web Caching" by Kai Cheng and Yahiko Kambayashi.
00055 
00056 // We keep kQueueCount LRU queues, which should be about ceil(log2(mHardLimit))
00057 // The queues hold exponentially increasing ranges of floor(log2((size/nref)))
00058 // values for entries.
00059 // Entries larger than 2^(kQueueCount-1) go in the last queue.
00060 // Entries with no expiration go in the first queue.
00061 
00062 const char *gMemoryDeviceID      = "memory";
00063 
00064 nsMemoryCacheDevice::nsMemoryCacheDevice()
00065     : mInitialized(PR_FALSE),
00066       mEvictionThreshold(PR_INT32_MAX),
00067       mHardLimit(4 * 1024 * 1024),       // default, if no pref
00068       mSoftLimit((mHardLimit * 9) / 10), // default, if no pref
00069       mTotalSize(0),
00070       mInactiveSize(0),
00071       mEntryCount(0),
00072       mMaxEntryCount(0)
00073 {
00074     for (int i=0; i<kQueueCount; ++i)
00075         PR_INIT_CLIST(&mEvictionList[i]);
00076 }
00077 
00078 
00079 nsMemoryCacheDevice::~nsMemoryCacheDevice()
00080 {    
00081     Shutdown();
00082 }
00083 
00084 
00085 nsresult
00086 nsMemoryCacheDevice::Init()
00087 {
00088     if (mInitialized)  return NS_ERROR_ALREADY_INITIALIZED;
00089 
00090     nsresult  rv = mMemCacheEntries.Init();
00091     mInitialized = NS_SUCCEEDED(rv);
00092     return rv;
00093 }
00094 
00095 
00096 nsresult
00097 nsMemoryCacheDevice::Shutdown()
00098 {
00099     NS_ASSERTION(mInitialized, "### attempting shutdown while not initialized");
00100     NS_ENSURE_TRUE(mInitialized, NS_ERROR_NOT_INITIALIZED);
00101     
00102     mMemCacheEntries.Shutdown();
00103 
00104     // evict all entries
00105     nsCacheEntry * entry, * next;
00106 
00107     for (int i = kQueueCount - 1; i >= 0; --i) {
00108         entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
00109         while (entry != &mEvictionList[i]) {
00110             NS_ASSERTION(entry->IsInUse() == PR_FALSE, "### shutting down with active entries.\n");
00111             next = (nsCacheEntry *)PR_NEXT_LINK(entry);
00112             PR_REMOVE_AND_INIT_LINK(entry);
00113         
00114             // update statistics
00115             PRInt32 memoryRecovered = (PRInt32)entry->Size();
00116             mTotalSize    -= memoryRecovered;
00117             mInactiveSize -= memoryRecovered;
00118             --mEntryCount;
00119 
00120             delete entry;
00121             entry = next;
00122         }
00123     }
00124 
00125 /*
00126  * we're not factoring in changes to meta data yet...    
00127  *  NS_ASSERTION(mTotalSize == 0, "### mem cache leaking entries?\n");
00128  */
00129     NS_ASSERTION(mInactiveSize == 0, "### mem cache leaking entries?\n");
00130     NS_ASSERTION(mEntryCount == 0, "### mem cache leaking entries?\n");
00131     
00132     mInitialized = PR_FALSE;
00133 
00134     return NS_OK;
00135 }
00136 
00137 
00138 const char *
00139 nsMemoryCacheDevice::GetDeviceID()
00140 {
00141     return gMemoryDeviceID;
00142 }
00143 
00144 
00145 nsCacheEntry *
00146 nsMemoryCacheDevice::FindEntry(nsCString * key, PRBool *collision)
00147 {
00148     nsCacheEntry * entry = mMemCacheEntries.GetEntry(key);
00149     if (!entry)  return nsnull;
00150 
00151     // move entry to the tail of an eviction list
00152     PR_REMOVE_AND_INIT_LINK(entry);
00153     PR_APPEND_LINK(entry, &mEvictionList[EvictionList(entry, 0)]);
00154     
00155     mInactiveSize -= entry->Size();
00156 
00157     return entry;
00158 }
00159 
00160 
00161 nsresult
00162 nsMemoryCacheDevice::DeactivateEntry(nsCacheEntry * entry)
00163 {
00164     if (entry->IsDoomed()) {
00165 #ifdef DEBUG
00166         // XXX verify we've removed it from mMemCacheEntries & eviction list
00167 #endif
00168         delete entry;
00169         return NS_OK;
00170     }
00171 
00172 #ifdef DEBUG
00173     nsCacheEntry * ourEntry = mMemCacheEntries.GetEntry(entry->Key());
00174     NS_ASSERTION(ourEntry, "DeactivateEntry called for an entry we don't have!");
00175     NS_ASSERTION(entry == ourEntry, "entry doesn't match ourEntry");
00176     if (ourEntry != entry)
00177         return NS_ERROR_INVALID_POINTER;
00178 #endif
00179 
00180     mInactiveSize += entry->Size();
00181     EvictEntriesIfNecessary();
00182 
00183     return NS_OK;
00184 }
00185 
00186 
00187 nsresult
00188 nsMemoryCacheDevice::BindEntry(nsCacheEntry * entry)
00189 {
00190        if (!entry->IsDoomed()) {
00191            NS_ASSERTION(PR_CLIST_IS_EMPTY(entry),"entry is already on a list!");
00192        
00193               // append entry to the eviction list
00194         PR_APPEND_LINK(entry, &mEvictionList[EvictionList(entry, 0)]);
00195 
00196         // add entry to hashtable of mem cache entries
00197         nsresult  rv = mMemCacheEntries.AddEntry(entry);
00198         if (NS_FAILED(rv)) {
00199             PR_REMOVE_AND_INIT_LINK(entry);
00200             return rv;
00201         }
00202        }
00203 
00204     // add size of entry to memory totals
00205     ++mEntryCount;
00206     if (mMaxEntryCount < mEntryCount) mMaxEntryCount = mEntryCount;
00207 
00208     mTotalSize += entry->Size();
00209     EvictEntriesIfNecessary();
00210     
00211     return NS_OK;
00212 }
00213 
00214 
00215 void
00216 nsMemoryCacheDevice::DoomEntry(nsCacheEntry * entry)
00217 {
00218 #ifdef DEBUG
00219     // debug code to verify we have entry
00220     nsCacheEntry * hashEntry = mMemCacheEntries.GetEntry(entry->Key());
00221     if (!hashEntry)               NS_WARNING("no entry for key");
00222     else if (entry != hashEntry)  NS_WARNING("entry != hashEntry");
00223 #endif
00224 
00225     EvictEntry(entry, DO_NOT_DELETE_ENTRY);
00226 }
00227 
00228 
00229 nsresult
00230 nsMemoryCacheDevice::OpenInputStreamForEntry( nsCacheEntry *    entry,
00231                                               nsCacheAccessMode mode,
00232                                               PRUint32          offset,
00233                                               nsIInputStream ** result)
00234 {
00235     NS_ENSURE_ARG_POINTER(entry);
00236     NS_ENSURE_ARG_POINTER(result);
00237 
00238     nsCOMPtr<nsIStorageStream> storage;
00239     nsresult rv;
00240 
00241     nsISupports *data = entry->Data();
00242     if (data) {
00243         storage = do_QueryInterface(data, &rv);
00244         if (NS_FAILED(rv))
00245             return rv;
00246     }
00247     else {
00248         rv = NS_NewStorageStream(4096, PRUint32(-1), getter_AddRefs(storage));
00249         if (NS_FAILED(rv))
00250             return rv;
00251         entry->SetData(storage);
00252     }
00253 
00254     return storage->NewInputStream(offset, result);
00255 }
00256 
00257 
00258 nsresult
00259 nsMemoryCacheDevice::OpenOutputStreamForEntry( nsCacheEntry *     entry,
00260                                                nsCacheAccessMode  mode,
00261                                                PRUint32           offset,
00262                                                nsIOutputStream ** result)
00263 {
00264     NS_ENSURE_ARG_POINTER(entry);
00265     NS_ENSURE_ARG_POINTER(result);
00266 
00267     nsCOMPtr<nsIStorageStream> storage;
00268     nsresult rv;
00269 
00270     nsISupports *data = entry->Data();
00271     if (data) {
00272         storage = do_QueryInterface(data, &rv);
00273         if (NS_FAILED(rv))
00274             return rv;
00275     }
00276     else {
00277         rv = NS_NewStorageStream(4096, PRUint32(-1), getter_AddRefs(storage));
00278         if (NS_FAILED(rv))
00279             return rv;
00280         entry->SetData(storage);
00281     }
00282 
00283     return storage->GetOutputStream(offset, result);
00284 }
00285 
00286 
00287 nsresult
00288 nsMemoryCacheDevice::GetFileForEntry( nsCacheEntry *    entry,
00289                                       nsIFile **        result )
00290 {
00291     return NS_ERROR_NOT_IMPLEMENTED;
00292 }
00293 
00294 
00295 nsresult
00296 nsMemoryCacheDevice::OnDataSizeChange( nsCacheEntry * entry, PRInt32 deltaSize)
00297 {
00298     if (entry->IsStreamData()) {
00299         // we have the right to refuse or pre-evict
00300         PRUint32  newSize = entry->DataSize() + deltaSize;
00301         if ((PRInt32) newSize > mSoftLimit) {
00302             nsresult rv = nsCacheService::DoomEntry(entry);
00303             NS_ASSERTION(NS_SUCCEEDED(rv),"DoomEntry() failed.");
00304             return NS_ERROR_ABORT;
00305         }
00306     }
00307 
00308     // adjust our totals
00309     mTotalSize    += deltaSize;
00310     
00311     if (!entry->IsDoomed()) {
00312         // move entry to the tail of the appropriate eviction list
00313         PR_REMOVE_AND_INIT_LINK(entry);
00314         PR_APPEND_LINK(entry, &mEvictionList[EvictionList(entry, deltaSize)]);
00315     }
00316 
00317     EvictEntriesIfNecessary();
00318     return NS_OK;
00319 }
00320 
00321 
00322 void
00323 nsMemoryCacheDevice::AdjustMemoryLimits(PRInt32  softLimit, PRInt32  hardLimit)
00324 {
00325     mSoftLimit = softLimit;
00326     mHardLimit = hardLimit;
00327 
00328     // First, evict entries that won't fit into the new cache size.
00329     EvictEntriesIfNecessary();
00330 }
00331 
00332 
00333 void
00334 nsMemoryCacheDevice::EvictEntry(nsCacheEntry * entry, PRBool deleteEntry)
00335 {
00336     // remove entry from our hashtable
00337     mMemCacheEntries.RemoveEntry(entry);
00338     
00339     // remove entry from the eviction list
00340     PR_REMOVE_AND_INIT_LINK(entry);
00341     
00342     // update statistics
00343     PRInt32 memoryRecovered = (PRInt32)entry->Size();
00344     mTotalSize    -= memoryRecovered;
00345     if (!entry->IsDoomed())
00346         mInactiveSize -= memoryRecovered;
00347     --mEntryCount;
00348     
00349     if (deleteEntry)  delete entry;
00350 }
00351 
00352 
00353 void
00354 nsMemoryCacheDevice::EvictEntriesIfNecessary(void)
00355 {
00356     nsCacheEntry * entry, * next;
00357 
00358     if ((mTotalSize < mHardLimit) && (mInactiveSize < mSoftLimit))
00359         return;
00360 
00361     for (int i = kQueueCount - 1; i >= 0; --i) {
00362         entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
00363         while (entry != &mEvictionList[i]) {
00364             if (entry->IsInUse()) {
00365                 entry = (nsCacheEntry *)PR_NEXT_LINK(entry);
00366                 continue;
00367             }
00368 
00369             next = (nsCacheEntry *)PR_NEXT_LINK(entry);
00370             EvictEntry(entry, DELETE_ENTRY);
00371             entry = next;
00372 
00373             if ((mTotalSize < mHardLimit) && (mInactiveSize < mSoftLimit))
00374                 return;
00375         }
00376     }
00377 }
00378 
00379 
00380 int
00381 nsMemoryCacheDevice::EvictionList(nsCacheEntry * entry, PRInt32  deltaSize)
00382 {
00383     // favor items which never expire by putting them in the lowest-index queue
00384     if (entry->ExpirationTime() == NO_EXPIRATION_TIME)
00385         return 0;
00386 
00387     // compute which eviction queue this entry should go into,
00388     // based on floor(log2(size/nref))
00389     PRInt32  size       = deltaSize + (PRInt32)entry->Size();
00390     PRInt32  fetchCount = PR_MAX(1, entry->FetchCount());
00391 
00392     return PR_MIN(PR_FloorLog2(size / fetchCount), kQueueCount - 1);
00393 }
00394 
00395 
00396 nsresult
00397 nsMemoryCacheDevice::Visit(nsICacheVisitor * visitor)
00398 {
00399     nsMemoryCacheDeviceInfo * deviceInfo = new nsMemoryCacheDeviceInfo(this);
00400     nsCOMPtr<nsICacheDeviceInfo> deviceRef(deviceInfo);
00401     if (!deviceInfo) return NS_ERROR_OUT_OF_MEMORY;
00402 
00403     PRBool keepGoing;
00404     nsresult rv = visitor->VisitDevice(gMemoryDeviceID, deviceInfo, &keepGoing);
00405     if (NS_FAILED(rv)) return rv;
00406 
00407     if (!keepGoing)
00408         return NS_OK;
00409 
00410     nsCacheEntry *              entry;
00411     nsCOMPtr<nsICacheEntryInfo> entryRef;
00412 
00413     for (int i = kQueueCount - 1; i >= 0; --i) {
00414         entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
00415         while (entry != &mEvictionList[i]) {
00416             nsCacheEntryInfo * entryInfo = new nsCacheEntryInfo(entry);
00417             if (!entryInfo) return NS_ERROR_OUT_OF_MEMORY;
00418             entryRef = entryInfo;
00419 
00420             rv = visitor->VisitEntry(gMemoryDeviceID, entryInfo, &keepGoing);
00421             entryInfo->DetachEntry();
00422             if (NS_FAILED(rv)) return rv;
00423             if (!keepGoing) break;
00424 
00425             entry = (nsCacheEntry *)PR_NEXT_LINK(entry);
00426         }
00427     }
00428     return NS_OK;
00429 }
00430 
00431 
00432 nsresult
00433 nsMemoryCacheDevice::EvictEntries(const char * clientID)
00434 {
00435     nsCacheEntry * entry;
00436     PRUint32 prefixLength = (clientID ? strlen(clientID) : 0);
00437 
00438     for (int i = kQueueCount - 1; i >= 0; --i) {
00439         PRCList * elem = PR_LIST_HEAD(&mEvictionList[i]);
00440         while (elem != &mEvictionList[i]) {
00441             entry = (nsCacheEntry *)elem;
00442             elem = PR_NEXT_LINK(elem);
00443             
00444             const char * key = entry->Key()->get();
00445             if (clientID && nsCRT::strncmp(clientID, key, prefixLength) != 0)
00446                 continue;
00447             
00448             if (entry->IsInUse()) {
00449                 nsresult rv = nsCacheService::DoomEntry(entry);
00450                 if (NS_FAILED(rv)) {
00451                     CACHE_LOG_WARNING(("memCache->EvictEntries() aborted: rv =%x", rv));
00452                     return rv;
00453                 }
00454             } else {
00455                 EvictEntry(entry, DELETE_ENTRY);
00456             }
00457         }
00458     }
00459 
00460     return NS_OK;
00461 }
00462 
00463 
00464 // WARNING: SetCapacity can get called before Init()
00465 void
00466 nsMemoryCacheDevice::SetCapacity(PRInt32  capacity)
00467 {
00468     PRInt32 hardLimit = capacity * 1024;  // convert k into bytes
00469     PRInt32 softLimit = (hardLimit * 9) / 10;
00470     AdjustMemoryLimits(softLimit, hardLimit);
00471 }
00472 
00473 
00474 #ifdef DEBUG
00475 class nsCacheHashCounter : public nsCacheEntryHashTable::Visitor {
00476 public:
00477     nsCacheHashCounter() : entryCount(0) {}
00478 
00479     PRBool  VisitEntry(nsCacheEntry * entry);
00480     PRInt32 entryCount;
00481 };
00482 
00483 
00484 PRBool nsCacheHashCounter::VisitEntry(nsCacheEntry * entry)
00485 {
00486     ++entryCount;
00487     return PR_TRUE;
00488 }
00489 
00490 
00491 void
00492 nsMemoryCacheDevice::CheckEntryCount()
00493 {
00494     if (!mInitialized)  return;
00495 
00496     PRInt32 evictionListCount = 0;
00497     for (int i=0; i<kQueueCount; ++i) {
00498         PRCList * elem = PR_LIST_HEAD(&mEvictionList[i]);
00499         while (elem != &mEvictionList[i]) {
00500             elem = PR_NEXT_LINK(elem);
00501             ++evictionListCount;
00502         }
00503     }
00504     NS_ASSERTION(mEntryCount == evictionListCount, "### mem cache badness");
00505 
00506     nsCacheHashCounter hash;
00507     mMemCacheEntries.VisitEntries(&hash);
00508     NS_ASSERTION(mEntryCount == hash.entryCount, "### mem cache badness");    
00509 }
00510 #endif
00511 
00512 /******************************************************************************
00513  * nsMemoryCacheDeviceInfo - for implementing about:cache
00514  *****************************************************************************/
00515 
00516 
00517 NS_IMPL_ISUPPORTS1(nsMemoryCacheDeviceInfo, nsICacheDeviceInfo)
00518 
00519 
00520 NS_IMETHODIMP
00521 nsMemoryCacheDeviceInfo::GetDescription(char ** result)
00522 {
00523     NS_ENSURE_ARG_POINTER(result);
00524     *result = nsCRT::strdup("Memory cache device");
00525     if (!*result) return NS_ERROR_OUT_OF_MEMORY;
00526     return NS_OK;
00527 }
00528 
00529 
00530 NS_IMETHODIMP
00531 nsMemoryCacheDeviceInfo::GetUsageReport(char ** result)
00532 {
00533     NS_ENSURE_ARG_POINTER(result);
00534     nsCString  buffer;
00535 
00536     buffer.AssignLiteral("\n<tr>\n<td><b>Inactive storage:</b></td>\n<td><tt> ");
00537     buffer.AppendInt(mDevice->mInactiveSize / 1024);
00538     buffer.AppendLiteral(" KiB</tt></td>\n</tr>\n");
00539     
00540     *result = ToNewCString(buffer);
00541     if (!*result) return NS_ERROR_OUT_OF_MEMORY;
00542     return NS_OK;
00543 }
00544 
00545 
00546 NS_IMETHODIMP
00547 nsMemoryCacheDeviceInfo::GetEntryCount(PRUint32 * result)
00548 {
00549     NS_ENSURE_ARG_POINTER(result);
00550     // XXX compare calculated count vs. mEntryCount
00551     *result = (PRUint32)mDevice->mEntryCount;
00552     return NS_OK;
00553 }
00554 
00555 
00556 NS_IMETHODIMP
00557 nsMemoryCacheDeviceInfo::GetTotalSize(PRUint32 * result)
00558 {
00559     NS_ENSURE_ARG_POINTER(result);
00560     *result = (PRUint32)mDevice->mTotalSize;
00561     return NS_OK;
00562 }
00563 
00564 
00565 NS_IMETHODIMP
00566 nsMemoryCacheDeviceInfo::GetMaximumSize(PRUint32 * result)
00567 {
00568     NS_ENSURE_ARG_POINTER(result);
00569     *result = (PRUint32)mDevice->mHardLimit;
00570     return NS_OK;
00571 }