netwerk/cache/src/nsMemoryCacheDevice.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  *
   3  * ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is nsMemoryCacheDevice.cpp, released
  17  * February 22, 2001.
  18  *
  19  * The Initial Developer of the Original Code is
  20  * Netscape Communications Corporation.
  21  * Portions created by the Initial Developer are Copyright (C) 2001
  22  * the Initial Developer. All Rights Reserved.
  23  *
  24  * Contributor(s):
  25  *   Gordon Sheridan, <gordon@netscape.com>
  26  *   Patrick C. Beard <beard@netscape.com>
  27  *   Brian Ryner <bryner@brianryner.com>
  28  *
  29  * Alternatively, the contents of this file may be used under the terms of
  30  * either the GNU General Public License Version 2 or later (the "GPL"), or
  31  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  32  * in which case the provisions of the GPL or the LGPL are applicable instead
  33  * of those above. If you wish to allow use of your version of this file only
  34  * under the terms of either the GPL or the LGPL, and not to allow others to
  35  * use your version of this file under the terms of the MPL, indicate your
  36  * decision by deleting the provisions above and replace them with the notice
  37  * and other provisions required by the GPL or the LGPL. If you do not delete
  38  * the provisions above, a recipient may use your version of this file under
  39  * the terms of any one of the MPL, the GPL or the LGPL.
  40  *
  41  * ***** END LICENSE BLOCK ***** */
  42
  43 #include "nsMemoryCacheDevice.h"
  44 #include "nsCacheService.h"
  45 #include "nsICacheService.h"
  46 #include "nsIStorageStream.h"
  47 #include "nsICacheVisitor.h"
  48 #include "nsCRT.h"
  49 #include "nsCache.h"
  50 #include "nsReadableUtils.h"
  51
  52 // The memory cache implements a variation of the "LRU-SP" caching algorithm
  53 // described in "LRU-SP: A Size-Adjusted and Popularity-Aware LRU Replacement
  54 // Algorithm for Web Caching" by Kai Cheng and Yahiko Kambayashi.
  55
  56 // We keep kQueueCount LRU queues, which should be about ceil(log2(mHardLimit))
  57 // The queues hold exponentially increasing ranges of floor(log2((size/nref)))
  58 // values for entries.
  59 // Entries larger than 2^(kQueueCount-1) go in the last queue.
  60 // Entries with no expiration go in the first queue.
  61
  62 const char *gMemoryDeviceID      = "memory";
  63
  64 nsMemoryCacheDevice::nsMemoryCacheDevice()
  65     : mInitialized(PR_FALSE),
  66       mEvictionThreshold(PR_INT32_MAX),
  67       mHardLimit(4 * 1024 * 1024),       // default, if no pref
  68       mSoftLimit((mHardLimit * 9) / 10), // default, if no pref
  69       mTotalSize(0),
  70       mInactiveSize(0),
  71       mEntryCount(0),
  72       mMaxEntryCount(0)
  73 {
  74     for (int i=0; i<kQueueCount; ++i)
  75         PR_INIT_CLIST(&mEvictionList[i]);
  76 }
  77
  78
  79 nsMemoryCacheDevice::~nsMemoryCacheDevice()
  80 {
  81     Shutdown();
  82 }
  83
  84
  85 nsresult
  86 nsMemoryCacheDevice::Init()
  87 {
  88     if (mInitialized)  return NS_ERROR_ALREADY_INITIALIZED;
  89
  90     nsresult  rv = mMemCacheEntries.Init();
  91     mInitialized = NS_SUCCEEDED(rv);
  92     return rv;
  93 }
  94
  95
  96 nsresult
  97 nsMemoryCacheDevice::Shutdown()
  98 {
  99     NS_ASSERTION(mInitialized, "### attempting shutdown while not initialized");
 100     NS_ENSURE_TRUE(mInitialized, NS_ERROR_NOT_INITIALIZED);
 101
 102     mMemCacheEntries.Shutdown();
 103
 104     // evict all entries
 105     nsCacheEntry * entry, * next;
 106
 107     for (int i = kQueueCount - 1; i >= 0; --i) {
 108         entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
 109         while (entry != &mEvictionList[i]) {
 110             NS_ASSERTION(entry->IsInUse() == PR_FALSE, "### shutting down with active entries");
 111             next = (nsCacheEntry *)PR_NEXT_LINK(entry);
 112             PR_REMOVE_AND_INIT_LINK(entry);
 113
 114             // update statistics
 115             PRInt32 memoryRecovered = (PRInt32)entry->Size();
 116             mTotalSize    -= memoryRecovered;
 117             mInactiveSize -= memoryRecovered;
 118             --mEntryCount;
 119
 120             delete entry;
 121             entry = next;
 122         }
 123     }
 124
 125 /*
 126  * we're not factoring in changes to meta data yet...
 127  *  NS_ASSERTION(mTotalSize == 0, "### mem cache leaking entries?");
 128  */
 129     NS_ASSERTION(mInactiveSize == 0, "### mem cache leaking entries?");
 130     NS_ASSERTION(mEntryCount == 0, "### mem cache leaking entries?");
 131
 132     mInitialized = PR_FALSE;
 133
 134     return NS_OK;
 135 }
 136
 137
 138 const char *
 139 nsMemoryCacheDevice::GetDeviceID()
 140 {
 141     return gMemoryDeviceID;
 142 }
 143
 144
 145 nsCacheEntry *
 146 nsMemoryCacheDevice::FindEntry(nsCString * key, PRBool *collision)
 147 {
 148     nsCacheEntry * entry = mMemCacheEntries.GetEntry(key);
 149     if (!entry)  return nsnull;
 150
 151     // move entry to the tail of an eviction list
 152     PR_REMOVE_AND_INIT_LINK(entry);
 153     PR_APPEND_LINK(entry, &mEvictionList[EvictionList(entry, 0)]);
 154
 155     mInactiveSize -= entry->Size();
 156
 157     return entry;
 158 }
 159
 160
 161 nsresult
 162 nsMemoryCacheDevice::DeactivateEntry(nsCacheEntry * entry)
 163 {
 164     CACHE_LOG_DEBUG(("nsMemoryCacheDevice::DeactivateEntry for entry 0x%p\n",
 165                      entry));
 166     if (entry->IsDoomed()) {
 167 #ifdef DEBUG
 168         // XXX verify we've removed it from mMemCacheEntries & eviction list
 169 #endif
 170         delete entry;
 171         CACHE_LOG_DEBUG(("deleted doomed entry 0x%p\n", entry));
 172         return NS_OK;
 173     }
 174
 175 #ifdef DEBUG
 176     nsCacheEntry * ourEntry = mMemCacheEntries.GetEntry(entry->Key());
 177     NS_ASSERTION(ourEntry, "DeactivateEntry called for an entry we don't have!");
 178     NS_ASSERTION(entry == ourEntry, "entry doesn't match ourEntry");
 179     if (ourEntry != entry)
 180         return NS_ERROR_INVALID_POINTER;
 181 #endif
 182
 183     mInactiveSize += entry->Size();
 184     EvictEntriesIfNecessary();
 185
 186     return NS_OK;
 187 }
 188
 189
 190 nsresult
 191 nsMemoryCacheDevice::BindEntry(nsCacheEntry * entry)
 192 {
 193         if (!entry->IsDoomed()) {
 194             NS_ASSERTION(PR_CLIST_IS_EMPTY(entry),"entry is already on a list!");
 195
 196                 // append entry to the eviction list
 197         PR_APPEND_LINK(entry, &mEvictionList[EvictionList(entry, 0)]);
 198
 199         // add entry to hashtable of mem cache entries
 200         nsresult  rv = mMemCacheEntries.AddEntry(entry);
 201         if (NS_FAILED(rv)) {
 202             PR_REMOVE_AND_INIT_LINK(entry);
 203             return rv;
 204         }
 205         }
 206
 207     // add size of entry to memory totals
 208     ++mEntryCount;
 209     if (mMaxEntryCount < mEntryCount) mMaxEntryCount = mEntryCount;
 210
 211     mTotalSize += entry->Size();
 212     EvictEntriesIfNecessary();
 213
 214     return NS_OK;
 215 }
 216
 217
 218 void
 219 nsMemoryCacheDevice::DoomEntry(nsCacheEntry * entry)
 220 {
 221 #ifdef DEBUG
 222     // debug code to verify we have entry
 223     nsCacheEntry * hashEntry = mMemCacheEntries.GetEntry(entry->Key());
 224     if (!hashEntry)               NS_WARNING("no entry for key");
 225     else if (entry != hashEntry)  NS_WARNING("entry != hashEntry");
 226 #endif
 227     CACHE_LOG_DEBUG(("Dooming entry 0x%p in memory cache\n", entry));
 228     EvictEntry(entry, DO_NOT_DELETE_ENTRY);
 229 }
 230
 231
 232 nsresult
 233 nsMemoryCacheDevice::OpenInputStreamForEntry( nsCacheEntry *    entry,
 234                                               nsCacheAccessMode mode,
 235                                               PRUint32          offset,
 236                                               nsIInputStream ** result)
 237 {
 238     NS_ENSURE_ARG_POINTER(entry);
 239     NS_ENSURE_ARG_POINTER(result);
 240
 241     nsCOMPtr<nsIStorageStream> storage;
 242     nsresult rv;
 243
 244     nsISupports *data = entry->Data();
 245     if (data) {
 246         storage = do_QueryInterface(data, &rv);
 247         if (NS_FAILED(rv))
 248             return rv;
 249     }
 250     else {
 251         rv = NS_NewStorageStream(4096, PRUint32(-1), getter_AddRefs(storage));
 252         if (NS_FAILED(rv))
 253             return rv;
 254         entry->SetData(storage);
 255     }
 256
 257     return storage->NewInputStream(offset, result);
 258 }
 259
 260
 261 nsresult
 262 nsMemoryCacheDevice::OpenOutputStreamForEntry( nsCacheEntry *     entry,
 263                                                nsCacheAccessMode  mode,
 264                                                PRUint32           offset,
 265                                                nsIOutputStream ** result)
 266 {
 267     NS_ENSURE_ARG_POINTER(entry);
 268     NS_ENSURE_ARG_POINTER(result);
 269
 270     nsCOMPtr<nsIStorageStream> storage;
 271     nsresult rv;
 272
 273     nsISupports *data = entry->Data();
 274     if (data) {
 275         storage = do_QueryInterface(data, &rv);
 276         if (NS_FAILED(rv))
 277             return rv;
 278     }
 279     else {
 280         rv = NS_NewStorageStream(4096, PRUint32(-1), getter_AddRefs(storage));
 281         if (NS_FAILED(rv))
 282             return rv;
 283         entry->SetData(storage);
 284     }
 285
 286     return storage->GetOutputStream(offset, result);
 287 }
 288
 289
 290 nsresult
 291 nsMemoryCacheDevice::GetFileForEntry( nsCacheEntry *    entry,
 292                                       nsIFile **        result )
 293 {
 294     return NS_ERROR_NOT_IMPLEMENTED;
 295 }
 296
 297
 298 nsresult
 299 nsMemoryCacheDevice::OnDataSizeChange( nsCacheEntry * entry, PRInt32 deltaSize)
 300 {
 301     if (entry->IsStreamData()) {
 302         // we have the right to refuse or pre-evict
 303         PRUint32  newSize = entry->DataSize() + deltaSize;
 304         if ((PRInt32) newSize > mSoftLimit) {
 305 #ifdef DEBUG
 306             nsresult rv =
 307 #endif
 308                 nsCacheService::DoomEntry(entry);
 309             NS_ASSERTION(NS_SUCCEEDED(rv),"DoomEntry() failed.");
 310             return NS_ERROR_ABORT;
 311         }
 312     }
 313
 314     // adjust our totals
 315     mTotalSize    += deltaSize;
 316
 317     if (!entry->IsDoomed()) {
 318         // move entry to the tail of the appropriate eviction list
 319         PR_REMOVE_AND_INIT_LINK(entry);
 320         PR_APPEND_LINK(entry, &mEvictionList[EvictionList(entry, deltaSize)]);
 321     }
 322
 323     EvictEntriesIfNecessary();
 324     return NS_OK;
 325 }
 326
 327
 328 void
 329 nsMemoryCacheDevice::AdjustMemoryLimits(PRInt32  softLimit, PRInt32  hardLimit)
 330 {
 331     mSoftLimit = softLimit;
 332     mHardLimit = hardLimit;
 333
 334     // First, evict entries that won't fit into the new cache size.
 335     EvictEntriesIfNecessary();
 336 }
 337
 338
 339 void
 340 nsMemoryCacheDevice::EvictEntry(nsCacheEntry * entry, PRBool deleteEntry)
 341 {
 342     CACHE_LOG_DEBUG(("Evicting entry 0x%p from memory cache, deleting: %d\n",
 343                      entry, deleteEntry));
 344     // remove entry from our hashtable
 345     mMemCacheEntries.RemoveEntry(entry);
 346
 347     // remove entry from the eviction list
 348     PR_REMOVE_AND_INIT_LINK(entry);
 349
 350     // update statistics
 351     PRInt32 memoryRecovered = (PRInt32)entry->Size();
 352     mTotalSize    -= memoryRecovered;
 353     if (!entry->IsDoomed())
 354         mInactiveSize -= memoryRecovered;
 355     --mEntryCount;
 356
 357     if (deleteEntry)  delete entry;
 358 }
 359
 360
 361 void
 362 nsMemoryCacheDevice::EvictEntriesIfNecessary(void)
 363 {
 364     nsCacheEntry * entry, * next;
 365
 366     CACHE_LOG_DEBUG(("EvictEntriesIfNecessary.  mTotalSize: %d, mHardLimit: %d,"
 367                      "mInactiveSize: %d, mSoftLimit: %d\n",
 368                      mTotalSize, mHardLimit, mInactiveSize, mSoftLimit));
 369
 370     if ((mTotalSize < mHardLimit) && (mInactiveSize < mSoftLimit))
 371         return;
 372
 373     for (int i = kQueueCount - 1; i >= 0; --i) {
 374         entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
 375         while (entry != &mEvictionList[i]) {
 376             if (entry->IsInUse()) {
 377                 entry = (nsCacheEntry *)PR_NEXT_LINK(entry);
 378                 continue;
 379             }
 380
 381             next = (nsCacheEntry *)PR_NEXT_LINK(entry);
 382             EvictEntry(entry, DELETE_ENTRY);
 383             entry = next;
 384
 385             if ((mTotalSize < mHardLimit) && (mInactiveSize < mSoftLimit))
 386                 return;
 387         }
 388     }
 389 }
 390
 391
 392 int
 393 nsMemoryCacheDevice::EvictionList(nsCacheEntry * entry, PRInt32  deltaSize)
 394 {
 395     // favor items which never expire by putting them in the lowest-index queue
 396     if (entry->ExpirationTime() == NO_EXPIRATION_TIME)
 397         return 0;
 398
 399     // compute which eviction queue this entry should go into,
 400     // based on floor(log2(size/nref))
 401     PRInt32  size       = deltaSize + (PRInt32)entry->Size();
 402     PRInt32  fetchCount = PR_MAX(1, entry->FetchCount());
 403
 404     return PR_MIN(PR_FloorLog2(size / fetchCount), kQueueCount - 1);
 405 }
 406
 407
 408 nsresult
 409 nsMemoryCacheDevice::Visit(nsICacheVisitor * visitor)
 410 {
 411     nsMemoryCacheDeviceInfo * deviceInfo = new nsMemoryCacheDeviceInfo(this);
 412     nsCOMPtr<nsICacheDeviceInfo> deviceRef(deviceInfo);
 413     if (!deviceInfo) return NS_ERROR_OUT_OF_MEMORY;
 414
 415     PRBool keepGoing;
 416     nsresult rv = visitor->VisitDevice(gMemoryDeviceID, deviceInfo, &keepGoing);
 417     if (NS_FAILED(rv)) return rv;
 418
 419     if (!keepGoing)
 420         return NS_OK;
 421
 422     nsCacheEntry *              entry;
 423     nsCOMPtr<nsICacheEntryInfo> entryRef;
 424
 425     for (int i = kQueueCount - 1; i >= 0; --i) {
 426         entry = (nsCacheEntry *)PR_LIST_HEAD(&mEvictionList[i]);
 427         while (entry != &mEvictionList[i]) {
 428             nsCacheEntryInfo * entryInfo = new nsCacheEntryInfo(entry);
 429             if (!entryInfo) return NS_ERROR_OUT_OF_MEMORY;
 430             entryRef = entryInfo;
 431
 432             rv = visitor->VisitEntry(gMemoryDeviceID, entryInfo, &keepGoing);
 433             entryInfo->DetachEntry();
 434             if (NS_FAILED(rv)) return rv;
 435             if (!keepGoing) break;
 436
 437             entry = (nsCacheEntry *)PR_NEXT_LINK(entry);
 438         }
 439     }
 440     return NS_OK;
 441 }
 442
 443
 444 nsresult
 445 nsMemoryCacheDevice::EvictEntries(const char * clientID)
 446 {
 447     nsCacheEntry * entry;
 448     PRUint32 prefixLength = (clientID ? strlen(clientID) : 0);
 449
 450     for (int i = kQueueCount - 1; i >= 0; --i) {
 451         PRCList * elem = PR_LIST_HEAD(&mEvictionList[i]);
 452         while (elem != &mEvictionList[i]) {
 453             entry = (nsCacheEntry *)elem;
 454             elem = PR_NEXT_LINK(elem);
 455
 456             const char * key = entry->Key()->get();
 457             if (clientID && nsCRT::strncmp(clientID, key, prefixLength) != 0)
 458                 continue;
 459
 460             if (entry->IsInUse()) {
 461                 nsresult rv = nsCacheService::DoomEntry(entry);
 462                 if (NS_FAILED(rv)) {
 463                     CACHE_LOG_WARNING(("memCache->EvictEntries() aborted: rv =%x", rv));
 464                     return rv;
 465                 }
 466             } else {
 467                 EvictEntry(entry, DELETE_ENTRY);
 468             }
 469         }
 470     }
 471
 472     return NS_OK;
 473 }
 474
 475
 476 // WARNING: SetCapacity can get called before Init()
 477 void
 478 nsMemoryCacheDevice::SetCapacity(PRInt32  capacity)
 479 {
 480     PRInt32 hardLimit = capacity * 1024;  // convert k into bytes
 481     PRInt32 softLimit = (hardLimit * 9) / 10;
 482     AdjustMemoryLimits(softLimit, hardLimit);
 483 }
 484
 485
 486 #ifdef DEBUG
 487 static PLDHashOperator
 488 CountEntry(PLDHashTable * table, PLDHashEntryHdr * hdr, PRUint32 number, void * arg)
 489 {
 490     PRInt32 *entryCount = (PRInt32 *)arg;
 491     ++(*entryCount);
 492     return PL_DHASH_NEXT;
 493 }
 494
 495 void
 496 nsMemoryCacheDevice::CheckEntryCount()
 497 {
 498     if (!mInitialized)  return;
 499
 500     PRInt32 evictionListCount = 0;
 501     for (int i=0; i<kQueueCount; ++i) {
 502         PRCList * elem = PR_LIST_HEAD(&mEvictionList[i]);
 503         while (elem != &mEvictionList[i]) {
 504             elem = PR_NEXT_LINK(elem);
 505             ++evictionListCount;
 506         }
 507     }
 508     NS_ASSERTION(mEntryCount == evictionListCount, "### mem cache badness");
 509
 510     PRInt32 entryCount = 0;
 511     mMemCacheEntries.VisitEntries(CountEntry, &entryCount);
 512     NS_ASSERTION(mEntryCount == entryCount, "### mem cache badness");
 513 }
 514 #endif
 515
 516 /******************************************************************************
 517  * nsMemoryCacheDeviceInfo - for implementing about:cache
 518  *****************************************************************************/
 519
 520
 521 NS_IMPL_ISUPPORTS1(nsMemoryCacheDeviceInfo, nsICacheDeviceInfo)
 522
 523
 524 NS_IMETHODIMP
 525 nsMemoryCacheDeviceInfo::GetDescription(char ** result)
 526 {
 527     NS_ENSURE_ARG_POINTER(result);
 528     *result = NS_strdup("Memory cache device");
 529     if (!*result) return NS_ERROR_OUT_OF_MEMORY;
 530     return NS_OK;
 531 }
 532
 533
 534 NS_IMETHODIMP
 535 nsMemoryCacheDeviceInfo::GetUsageReport(char ** result)
 536 {
 537     NS_ENSURE_ARG_POINTER(result);
 538     nsCString  buffer;
 539
 540     buffer.AssignLiteral("\n<tr>\n<td><b>Inactive storage:</b></td>\n<td><tt> ");
 541     buffer.AppendInt(mDevice->mInactiveSize / 1024);
 542     buffer.AppendLiteral(" KiB</tt></td>\n</tr>\n");
 543
 544     *result = ToNewCString(buffer);
 545     if (!*result) return NS_ERROR_OUT_OF_MEMORY;
 546     return NS_OK;
 547 }
 548
 549
 550 NS_IMETHODIMP
 551 nsMemoryCacheDeviceInfo::GetEntryCount(PRUint32 * result)
 552 {
 553     NS_ENSURE_ARG_POINTER(result);
 554     // XXX compare calculated count vs. mEntryCount
 555     *result = (PRUint32)mDevice->mEntryCount;
 556     return NS_OK;
 557 }
 558
 559
 560 NS_IMETHODIMP
 561 nsMemoryCacheDeviceInfo::GetTotalSize(PRUint32 * result)
 562 {
 563     NS_ENSURE_ARG_POINTER(result);
 564     *result = (PRUint32)mDevice->mTotalSize;
 565     return NS_OK;
 566 }
 567
 568
 569 NS_IMETHODIMP
 570 nsMemoryCacheDeviceInfo::GetMaximumSize(PRUint32 * result)
 571 {
 572     NS_ENSURE_ARG_POINTER(result);
 573     *result = (PRUint32)mDevice->mHardLimit;
 574     return NS_OK;
 575 }