netwerk/cache/nsMemoryCacheDevice.cpp

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