third_party/WebKit/Source/core/fetch/MemoryCache.cpp

   1 /*
   2     Copyright (C) 1998 Lars Knoll (knoll@mpi-hd.mpg.de)
   3     Copyright (C) 2001 Dirk Mueller (mueller@kde.org)
   4     Copyright (C) 2002 Waldo Bastian (bastian@kde.org)
   5     Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   6
   7     This library is free software; you can redistribute it and/or
   8     modify it under the terms of the GNU Library General Public
   9     License as published by the Free Software Foundation; either
  10     version 2 of the License, or (at your option) any later version.
  11
  12     This library is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15     Library General Public License for more details.
  16
  17     You should have received a copy of the GNU Library General Public License
  18     along with this library; see the file COPYING.LIB.  If not, write to
  19     the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  20     Boston, MA 02110-1301, USA.
  21 */
  22
  23 #include "config.h"
  24 #include "core/fetch/MemoryCache.h"
  25
  26 #include "core/fetch/ResourcePtr.h"
  27 #include "platform/Logging.h"
  28 #include "platform/TraceEvent.h"
  29 #include "platform/weborigin/SecurityOrigin.h"
  30 #include "platform/weborigin/SecurityOriginHash.h"
  31 #include "public/platform/Platform.h"
  32 #include "wtf/Assertions.h"
  33 #include "wtf/CurrentTime.h"
  34 #include "wtf/MainThread.h"
  35 #include "wtf/MathExtras.h"
  36 #include "wtf/TemporaryChange.h"
  37 #include "wtf/text/CString.h"
  38
  39 namespace blink {
  40
  41 static Persistent<MemoryCache>* gMemoryCache;
  42
  43 static const unsigned cDefaultCacheCapacity = 8192 * 1024;
  44 static const unsigned cDeferredPruneDeadCapacityFactor = 2;
  45 static const int cMinDelayBeforeLiveDecodedPrune = 1; // Seconds.
  46 static const double cMaxPruneDeferralDelay = 0.5; // Seconds.
  47 static const float cTargetPrunePercentage = .95f; // Percentage of capacity toward which we prune, to avoid immediately pruning again.
  48
  49 MemoryCache* memoryCache()
  50 {
  51     ASSERT(WTF::isMainThread());
  52     if (!gMemoryCache)
  53         gMemoryCache = new Persistent<MemoryCache>(MemoryCache::create());
  54     return gMemoryCache->get();
  55 }
  56
  57 MemoryCache* replaceMemoryCacheForTesting(MemoryCache* cache)
  58 {
  59 #if ENABLE(OILPAN)
  60     // Move m_liveResources content to keep Resource objects alive.
  61     for (const auto& resource : memoryCache()->m_liveResources)
  62         cache->m_liveResources.add(resource);
  63     memoryCache()->m_liveResources.clear();
  64 #endif
  65     memoryCache();
  66     MemoryCache* oldCache = gMemoryCache->release();
  67     *gMemoryCache = cache;
  68     return oldCache;
  69 }
  70
  71 DEFINE_TRACE(MemoryCacheEntry)
  72 {
  73     visitor->trace(m_previousInLiveResourcesList);
  74     visitor->trace(m_nextInLiveResourcesList);
  75     visitor->trace(m_previousInAllResourcesList);
  76     visitor->trace(m_nextInAllResourcesList);
  77 }
  78
  79 void MemoryCacheEntry::dispose()
  80 {
  81     m_resource.clear();
  82 }
  83
  84 DEFINE_TRACE(MemoryCacheLRUList)
  85 {
  86     visitor->trace(m_head);
  87     visitor->trace(m_tail);
  88 }
  89
  90 inline MemoryCache::MemoryCache()
  91     : m_inPruneResources(false)
  92     , m_prunePending(false)
  93     , m_maxPruneDeferralDelay(cMaxPruneDeferralDelay)
  94     , m_pruneTimeStamp(0.0)
  95     , m_pruneFrameTimeStamp(0.0)
  96     , m_lastFramePaintTimeStamp(0.0)
  97     , m_capacity(cDefaultCacheCapacity)
  98     , m_minDeadCapacity(0)
  99     , m_maxDeadCapacity(cDefaultCacheCapacity)
 100     , m_maxDeferredPruneDeadCapacity(cDeferredPruneDeadCapacityFactor * cDefaultCacheCapacity)
 101     , m_delayBeforeLiveDecodedPrune(cMinDelayBeforeLiveDecodedPrune)
 102     , m_liveSize(0)
 103     , m_deadSize(0)
 104 #ifdef MEMORY_CACHE_STATS
 105     , m_statsTimer(this, &MemoryCache::dumpStats)
 106 #endif
 107 {
 108 #ifdef MEMORY_CACHE_STATS
 109     const double statsIntervalInSeconds = 15;
 110     m_statsTimer.startRepeating(statsIntervalInSeconds, FROM_HERE);
 111 #endif
 112 }
 113
 114 MemoryCache* MemoryCache::create()
 115 {
 116     return new MemoryCache;
 117 }
 118
 119 MemoryCache::~MemoryCache()
 120 {
 121     if (m_prunePending)
 122         Platform::current()->currentThread()->removeTaskObserver(this);
 123 }
 124
 125 DEFINE_TRACE(MemoryCache)
 126 {
 127     visitor->trace(m_allResources);
 128     for (size_t i = 0; i < WTF_ARRAY_LENGTH(m_liveDecodedResources); ++i)
 129         visitor->trace(m_liveDecodedResources[i]);
 130     visitor->trace(m_resourceMaps);
 131 #if ENABLE(OILPAN)
 132     visitor->trace(m_liveResources);
 133 #endif
 134 }
 135
 136 KURL MemoryCache::removeFragmentIdentifierIfNeeded(const KURL& originalURL)
 137 {
 138     if (!originalURL.hasFragmentIdentifier())
 139         return originalURL;
 140     // Strip away fragment identifier from HTTP URLs.
 141     // Data URLs must be unmodified. For file and custom URLs clients may expect resources
 142     // to be unique even when they differ by the fragment identifier only.
 143     if (!originalURL.protocolIsInHTTPFamily())
 144         return originalURL;
 145     KURL url = originalURL;
 146     url.removeFragmentIdentifier();
 147     return url;
 148 }
 149
 150 String MemoryCache::defaultCacheIdentifier()
 151 {
 152     return emptyString();
 153 }
 154
 155 MemoryCache::ResourceMap* MemoryCache::ensureResourceMap(const String& cacheIdentifier)
 156 {
 157     if (!m_resourceMaps.contains(cacheIdentifier)) {
 158         ResourceMapIndex::AddResult result = m_resourceMaps.add(cacheIdentifier, new ResourceMap);
 159         RELEASE_ASSERT(result.isNewEntry);
 160     }
 161     return m_resourceMaps.get(cacheIdentifier);
 162 }
 163
 164 void MemoryCache::add(Resource* resource)
 165 {
 166     ASSERT(WTF::isMainThread());
 167     ASSERT(resource->url().isValid());
 168     ResourceMap* resources = ensureResourceMap(resource->cacheIdentifier());
 169     RELEASE_ASSERT(!resources->contains(resource->url()));
 170     resources->set(resource->url(), MemoryCacheEntry::create(resource));
 171     update(resource, 0, resource->size(), true);
 172
 173     WTF_LOG(ResourceLoading, "MemoryCache::add Added '%s', resource %p\n", resource->url().string().latin1().data(), resource);
 174 }
 175
 176 void MemoryCache::replace(Resource* newResource, Resource* oldResource)
 177 {
 178     ASSERT(newResource->cacheIdentifier() == oldResource->cacheIdentifier());
 179     ResourceMap* resources = ensureResourceMap(oldResource->cacheIdentifier());
 180     if (MemoryCacheEntry* oldEntry = resources->get(oldResource->url()))
 181         evict(oldEntry);
 182     add(newResource);
 183     if (newResource->decodedSize() && newResource->hasClients())
 184         insertInLiveDecodedResourcesList(resources->get(newResource->url()));
 185 }
 186
 187 void MemoryCache::remove(Resource* resource)
 188 {
 189     // The resource may have already been removed by someone other than our caller,
 190     // who needed a fresh copy for a reload.
 191     if (MemoryCacheEntry* entry = getEntryForResource(resource))
 192         evict(entry);
 193 }
 194
 195 bool MemoryCache::contains(const Resource* resource) const
 196 {
 197     return getEntryForResource(resource);
 198 }
 199
 200 Resource* MemoryCache::resourceForURL(const KURL& resourceURL)
 201 {
 202     return resourceForURL(resourceURL, defaultCacheIdentifier());
 203 }
 204
 205 Resource* MemoryCache::resourceForURL(const KURL& resourceURL, const String& cacheIdentifier)
 206 {
 207     ASSERT(WTF::isMainThread());
 208     if (!resourceURL.isValid() || resourceURL.isNull())
 209         return nullptr;
 210     ASSERT(!cacheIdentifier.isNull());
 211     ResourceMap* resources = m_resourceMaps.get(cacheIdentifier);
 212     if (!resources)
 213         return nullptr;
 214     KURL url = removeFragmentIdentifierIfNeeded(resourceURL);
 215     MemoryCacheEntry* entry = resources->get(url);
 216     if (!entry)
 217         return nullptr;
 218     Resource* resource = entry->m_resource.get();
 219     if (resource && !resource->lock()) {
 220         ASSERT(!resource->hasClients());
 221         bool didEvict = evict(entry);
 222         ASSERT_UNUSED(didEvict, didEvict);
 223         return nullptr;
 224     }
 225     return resource;
 226 }
 227
 228 WillBeHeapVector<RawPtrWillBeMember<Resource>> MemoryCache::resourcesForURL(const KURL& resourceURL)
 229 {
 230     ASSERT(WTF::isMainThread());
 231     KURL url = removeFragmentIdentifierIfNeeded(resourceURL);
 232     WillBeHeapVector<RawPtrWillBeMember<Resource>> results;
 233     for (const auto& resourceMapIter : m_resourceMaps) {
 234         if (MemoryCacheEntry* entry = resourceMapIter.value->get(url))
 235             results.append(entry->m_resource.get());
 236     }
 237     return results;
 238 }
 239
 240 size_t MemoryCache::deadCapacity() const
 241 {
 242     // Dead resource capacity is whatever space is not occupied by live resources, bounded by an independent minimum and maximum.
 243     size_t capacity = m_capacity - std::min(m_liveSize, m_capacity); // Start with available capacity.
 244     capacity = std::max(capacity, m_minDeadCapacity); // Make sure it's above the minimum.
 245     capacity = std::min(capacity, m_maxDeadCapacity); // Make sure it's below the maximum.
 246     return capacity;
 247 }
 248
 249 size_t MemoryCache::liveCapacity() const
 250 {
 251     // Live resource capacity is whatever is left over after calculating dead resource capacity.
 252     return m_capacity - deadCapacity();
 253 }
 254
 255 void MemoryCache::pruneLiveResources(PruneStrategy strategy)
 256 {
 257     ASSERT(!m_prunePending);
 258     size_t capacity = liveCapacity();
 259     if (strategy == MaximalPrune)
 260         capacity = 0;
 261     if (!m_liveSize || (capacity && m_liveSize <= capacity))
 262         return;
 263
 264     size_t targetSize = static_cast<size_t>(capacity * cTargetPrunePercentage); // Cut by a percentage to avoid immediately pruning again.
 265
 266     // Destroy any decoded data in live objects that we can.
 267     // Start from the tail, since this is the lowest priority
 268     // and least recently accessed of the objects.
 269
 270     // The list might not be sorted by the m_lastDecodedFrameTimeStamp. The impact
 271     // of this weaker invariant is minor as the below if statement to check the
 272     // elapsedTime will evaluate to false as the current time will be a lot
 273     // greater than the current->m_lastDecodedFrameTimeStamp.
 274     // For more details see: https://bugs.webkit.org/show_bug.cgi?id=30209
 275
 276     // Start pruning from the lowest priority list.
 277     for (int priority = MemoryCacheLiveResourcePriorityLow; priority <= MemoryCacheLiveResourcePriorityHigh; ++priority) {
 278         MemoryCacheEntry* current = m_liveDecodedResources[priority].m_tail;
 279         while (current) {
 280             MemoryCacheEntry* previous = current->m_previousInLiveResourcesList;
 281             ASSERT(current->m_resource->hasClients());
 282             if (current->m_resource->isLoaded() && current->m_resource->decodedSize()) {
 283                 // Check to see if the remaining resources are too new to prune.
 284                 double elapsedTime = m_pruneFrameTimeStamp - current->m_lastDecodedAccessTime;
 285                 if (strategy == AutomaticPrune && elapsedTime < m_delayBeforeLiveDecodedPrune)
 286                     return;
 287
 288                 // Destroy our decoded data if possible. This will remove us
 289                 // from m_liveDecodedResources, and possibly move us to a
 290                 // different LRU list in m_allResources.
 291                 current->m_resource->prune();
 292
 293                 if (targetSize && m_liveSize <= targetSize)
 294                     return;
 295             }
 296             current = previous;
 297         }
 298     }
 299 }
 300
 301 void MemoryCache::pruneDeadResources(PruneStrategy strategy)
 302 {
 303     size_t capacity = deadCapacity();
 304     if (strategy == MaximalPrune)
 305         capacity = 0;
 306     if (!m_deadSize || (capacity && m_deadSize <= capacity))
 307         return;
 308
 309     size_t targetSize = static_cast<size_t>(capacity * cTargetPrunePercentage); // Cut by a percentage to avoid immediately pruning again.
 310
 311     int size = m_allResources.size();
 312
 313     // See if we have any purged resources we can evict.
 314     for (int i = 0; i < size; i++) {
 315         MemoryCacheEntry* current = m_allResources[i].m_tail;
 316         while (current) {
 317             MemoryCacheEntry* previous = current->m_previousInAllResourcesList;
 318             // Main Resources in the cache are only substitue data that was
 319             // precached and should not be evicted.
 320             if (current->m_resource->wasPurged() && current->m_resource->canDelete()
 321                 && current->m_resource->type() != Resource::MainResource) {
 322                 ASSERT(!current->m_resource->hasClients());
 323                 ASSERT(!current->m_resource->isPreloaded());
 324                 bool wasEvicted = evict(current);
 325                 ASSERT_UNUSED(wasEvicted, wasEvicted);
 326             }
 327             current = previous;
 328         }
 329     }
 330     if (targetSize && m_deadSize <= targetSize)
 331         return;
 332
 333     bool canShrinkLRULists = true;
 334     for (int i = size - 1; i >= 0; i--) {
 335         // Remove from the tail, since this is the least frequently accessed of the objects.
 336         MemoryCacheEntry* current = m_allResources[i].m_tail;
 337
 338         // First flush all the decoded data in this queue.
 339         while (current) {
 340             // Protect 'previous' so it can't get deleted during destroyDecodedData().
 341             MemoryCacheEntry* previous = current->m_previousInAllResourcesList;
 342             ASSERT(!previous || contains(previous->m_resource.get()));
 343             if (!current->m_resource->hasClients() && !current->m_resource->isPreloaded() && current->m_resource->isLoaded()) {
 344                 // Destroy our decoded data. This will remove us from
 345                 // m_liveDecodedResources, and possibly move us to a different
 346                 // LRU list in m_allResources.
 347                 current->m_resource->prune();
 348
 349                 if (targetSize && m_deadSize <= targetSize)
 350                     return;
 351             }
 352             // Decoded data may reference other resources. Stop iterating if 'previous' somehow got
 353             // kicked out of cache during destroyDecodedData().
 354             if (previous && !contains(previous->m_resource.get()))
 355                 break;
 356             current = previous;
 357         }
 358
 359         // Now evict objects from this queue.
 360         current = m_allResources[i].m_tail;
 361         while (current) {
 362             MemoryCacheEntry* previous = current->m_previousInAllResourcesList;
 363             ASSERT(!previous || contains(previous->m_resource.get()));
 364             if (!current->m_resource->hasClients() && !current->m_resource->isPreloaded()
 365                 && !current->m_resource->isCacheValidator() && current->m_resource->canDelete()
 366                 && current->m_resource->type() != Resource::MainResource) {
 367                 // Main Resources in the cache are only substitue data that was
 368                 // precached and should not be evicted.
 369                 bool wasEvicted = evict(current);
 370                 ASSERT_UNUSED(wasEvicted, wasEvicted);
 371                 if (targetSize && m_deadSize <= targetSize)
 372                     return;
 373             }
 374             if (previous && !contains(previous->m_resource.get()))
 375                 break;
 376             current = previous;
 377         }
 378
 379         // Shrink the vector back down so we don't waste time inspecting
 380         // empty LRU lists on future prunes.
 381         if (m_allResources[i].m_head)
 382             canShrinkLRULists = false;
 383         else if (canShrinkLRULists)
 384             m_allResources.resize(i);
 385     }
 386 }
 387
 388 void MemoryCache::setCapacities(size_t minDeadBytes, size_t maxDeadBytes, size_t totalBytes)
 389 {
 390     ASSERT(minDeadBytes <= maxDeadBytes);
 391     ASSERT(maxDeadBytes <= totalBytes);
 392     m_minDeadCapacity = minDeadBytes;
 393     m_maxDeadCapacity = maxDeadBytes;
 394     m_maxDeferredPruneDeadCapacity = cDeferredPruneDeadCapacityFactor * maxDeadBytes;
 395     m_capacity = totalBytes;
 396     prune();
 397 }
 398
 399 bool MemoryCache::evict(MemoryCacheEntry* entry)
 400 {
 401     ASSERT(WTF::isMainThread());
 402
 403     Resource* resource = entry->m_resource.get();
 404     bool canDelete = resource->canDelete();
 405     WTF_LOG(ResourceLoading, "Evicting resource %p for '%s' from cache", resource, resource->url().string().latin1().data());
 406     // The resource may have already been removed by someone other than our caller,
 407     // who needed a fresh copy for a reload. See <http://bugs.webkit.org/show_bug.cgi?id=12479#c6>.
 408     update(resource, resource->size(), 0, false);
 409     removeFromLiveDecodedResourcesList(entry);
 410
 411     ResourceMap* resources = m_resourceMaps.get(resource->cacheIdentifier());
 412     ASSERT(resources);
 413     ResourceMap::iterator it = resources->find(resource->url());
 414     ASSERT(it != resources->end());
 415
 416     MemoryCacheEntry* entryPtr = it->value;
 417     resources->remove(it);
 418     if (entryPtr)
 419         entryPtr->dispose();
 420
 421     return canDelete;
 422 }
 423
 424 MemoryCacheEntry* MemoryCache::getEntryForResource(const Resource* resource) const
 425 {
 426     if (resource->url().isNull() || resource->url().isEmpty())
 427         return nullptr;
 428     ResourceMap* resources = m_resourceMaps.get(resource->cacheIdentifier());
 429     if (!resources)
 430         return nullptr;
 431     MemoryCacheEntry* entry = resources->get(resource->url());
 432     if (!entry || entry->m_resource != resource)
 433         return nullptr;
 434     return entry;
 435 }
 436
 437 MemoryCacheLRUList* MemoryCache::lruListFor(unsigned accessCount, size_t size)
 438 {
 439     ASSERT(accessCount > 0);
 440     unsigned queueIndex = WTF::fastLog2(size / accessCount);
 441     if (m_allResources.size() <= queueIndex)
 442         m_allResources.grow(queueIndex + 1);
 443     return &m_allResources[queueIndex];
 444 }
 445
 446 void MemoryCache::removeFromLRUList(MemoryCacheEntry* entry, MemoryCacheLRUList* list)
 447 {
 448     ASSERT(containedInLRUList(entry, list));
 449
 450     MemoryCacheEntry* next = entry->m_nextInAllResourcesList;
 451     MemoryCacheEntry* previous = entry->m_previousInAllResourcesList;
 452     entry->m_nextInAllResourcesList = nullptr;
 453     entry->m_previousInAllResourcesList = nullptr;
 454
 455     if (next)
 456         next->m_previousInAllResourcesList = previous;
 457     else
 458         list->m_tail = previous;
 459
 460     if (previous)
 461         previous->m_nextInAllResourcesList = next;
 462     else
 463         list->m_head = next;
 464
 465     ASSERT(!containedInLRUList(entry, list));
 466 }
 467
 468 void MemoryCache::insertInLRUList(MemoryCacheEntry* entry, MemoryCacheLRUList* list)
 469 {
 470     ASSERT(!containedInLRUList(entry, list));
 471
 472     entry->m_nextInAllResourcesList = list->m_head;
 473     list->m_head = entry;
 474
 475     if (entry->m_nextInAllResourcesList)
 476         entry->m_nextInAllResourcesList->m_previousInAllResourcesList = entry;
 477     else
 478         list->m_tail = entry;
 479
 480     ASSERT(containedInLRUList(entry, list));
 481 }
 482
 483 bool MemoryCache::containedInLRUList(MemoryCacheEntry* entry, MemoryCacheLRUList* list)
 484 {
 485     for (MemoryCacheEntry* current = list->m_head; current; current = current->m_nextInAllResourcesList) {
 486         if (current == entry)
 487             return true;
 488     }
 489     ASSERT(!entry->m_nextInAllResourcesList && !entry->m_previousInAllResourcesList);
 490     return false;
 491 }
 492
 493 void MemoryCache::removeFromLiveDecodedResourcesList(MemoryCacheEntry* entry)
 494 {
 495     // If we've never been accessed, then we're brand new and not in any list.
 496     if (!entry->m_inLiveDecodedResourcesList)
 497         return;
 498     ASSERT(containedInLiveDecodedResourcesList(entry));
 499
 500     entry->m_inLiveDecodedResourcesList = false;
 501
 502     MemoryCacheLRUList* list = &m_liveDecodedResources[entry->m_liveResourcePriority];
 503
 504     MemoryCacheEntry* next = entry->m_nextInLiveResourcesList;
 505     MemoryCacheEntry* previous = entry->m_previousInLiveResourcesList;
 506
 507     entry->m_nextInLiveResourcesList = nullptr;
 508     entry->m_previousInLiveResourcesList = nullptr;
 509
 510     if (next)
 511         next->m_previousInLiveResourcesList = previous;
 512     else
 513         list->m_tail = previous;
 514
 515     if (previous)
 516         previous->m_nextInLiveResourcesList = next;
 517     else
 518         list->m_head = next;
 519
 520     ASSERT(!containedInLiveDecodedResourcesList(entry));
 521 }
 522
 523 void MemoryCache::insertInLiveDecodedResourcesList(MemoryCacheEntry* entry)
 524 {
 525     ASSERT(!containedInLiveDecodedResourcesList(entry));
 526
 527     entry->m_inLiveDecodedResourcesList = true;
 528
 529     MemoryCacheLRUList* list = &m_liveDecodedResources[entry->m_liveResourcePriority];
 530     entry->m_nextInLiveResourcesList = list->m_head;
 531     if (list->m_head)
 532         list->m_head->m_previousInLiveResourcesList = entry;
 533     list->m_head = entry;
 534
 535     if (!entry->m_nextInLiveResourcesList)
 536         list->m_tail = entry;
 537
 538     ASSERT(containedInLiveDecodedResourcesList(entry));
 539 }
 540
 541 bool MemoryCache::containedInLiveDecodedResourcesList(MemoryCacheEntry* entry)
 542 {
 543     MemoryCacheLRUList* list = &m_liveDecodedResources[entry->m_liveResourcePriority];
 544     for (MemoryCacheEntry* current = list->m_head; current; current = current->m_nextInLiveResourcesList) {
 545         if (current == entry) {
 546             ASSERT(entry->m_inLiveDecodedResourcesList);
 547             return true;
 548         }
 549     }
 550     ASSERT(!entry->m_nextInLiveResourcesList && !entry->m_previousInLiveResourcesList && !entry->m_inLiveDecodedResourcesList);
 551     return false;
 552 }
 553
 554 void MemoryCache::makeLive(Resource* resource)
 555 {
 556     if (!contains(resource))
 557         return;
 558     ASSERT(m_deadSize >= resource->size());
 559     m_liveSize += resource->size();
 560     m_deadSize -= resource->size();
 561 }
 562
 563 void MemoryCache::makeDead(Resource* resource)
 564 {
 565     if (!contains(resource))
 566         return;
 567     m_liveSize -= resource->size();
 568     m_deadSize += resource->size();
 569     removeFromLiveDecodedResourcesList(getEntryForResource(resource));
 570 }
 571
 572 void MemoryCache::update(Resource* resource, size_t oldSize, size_t newSize, bool wasAccessed)
 573 {
 574     MemoryCacheEntry* entry = getEntryForResource(resource);
 575     if (!entry)
 576         return;
 577
 578     // The object must now be moved to a different queue, since either its size or its accessCount has been changed,
 579     // and both of those are used to determine which LRU queue the resource should be in.
 580     if (oldSize)
 581         removeFromLRUList(entry, lruListFor(entry->m_accessCount, oldSize));
 582     if (wasAccessed)
 583         entry->m_accessCount++;
 584     if (newSize)
 585         insertInLRUList(entry, lruListFor(entry->m_accessCount, newSize));
 586
 587     ptrdiff_t delta = newSize - oldSize;
 588     if (resource->hasClients()) {
 589         ASSERT(delta >= 0 || m_liveSize >= static_cast<size_t>(-delta) );
 590         m_liveSize += delta;
 591     } else {
 592         ASSERT(delta >= 0 || m_deadSize >= static_cast<size_t>(-delta) );
 593         m_deadSize += delta;
 594     }
 595 }
 596
 597 void MemoryCache::updateDecodedResource(Resource* resource, UpdateReason reason, MemoryCacheLiveResourcePriority priority)
 598 {
 599     MemoryCacheEntry* entry = getEntryForResource(resource);
 600     if (!entry)
 601         return;
 602
 603     removeFromLiveDecodedResourcesList(entry);
 604     if (priority != MemoryCacheLiveResourcePriorityUnknown && priority != entry->m_liveResourcePriority)
 605         entry->m_liveResourcePriority = priority;
 606     if (resource->decodedSize() && resource->hasClients())
 607         insertInLiveDecodedResourcesList(entry);
 608
 609     if (reason != UpdateForAccess)
 610         return;
 611
 612     double timestamp = resource->isImage() ? m_lastFramePaintTimeStamp : 0.0;
 613     if (!timestamp)
 614         timestamp = currentTime();
 615     entry->m_lastDecodedAccessTime = timestamp;
 616 }
 617
 618 MemoryCacheLiveResourcePriority MemoryCache::priority(Resource* resource) const
 619 {
 620     MemoryCacheEntry* entry = getEntryForResource(resource);
 621     if (!entry)
 622         return MemoryCacheLiveResourcePriorityUnknown;
 623     return entry->m_liveResourcePriority;
 624 }
 625
 626 void MemoryCache::removeURLFromCache(const KURL& url)
 627 {
 628     WillBeHeapVector<RawPtrWillBeMember<Resource>> resources = resourcesForURL(url);
 629     for (Resource* resource : resources)
 630         memoryCache()->remove(resource);
 631 }
 632
 633 void MemoryCache::TypeStatistic::addResource(Resource* o)
 634 {
 635     bool purged = o->wasPurged();
 636     bool purgeable = o->isPurgeable() && !purged;
 637     size_t pageSize = (o->encodedSize() + o->overheadSize() + 4095) & ~4095;
 638     count++;
 639     size += purged ? 0 : o->size();
 640     liveSize += o->hasClients() ? o->size() : 0;
 641     decodedSize += o->decodedSize();
 642     encodedSize += o->encodedSize();
 643     encodedSizeDuplicatedInDataURLs += o->url().protocolIsData() ? o->encodedSize() : 0;
 644     purgeableSize += purgeable ? pageSize : 0;
 645     purgedSize += purged ? pageSize : 0;
 646 }
 647
 648 MemoryCache::Statistics MemoryCache::getStatistics()
 649 {
 650     Statistics stats;
 651     for (const auto& resourceMapIter : m_resourceMaps) {
 652         for (const auto& resourceIter : *resourceMapIter.value) {
 653             Resource* resource = resourceIter.value->m_resource.get();
 654             switch (resource->type()) {
 655             case Resource::Image:
 656                 stats.images.addResource(resource);
 657                 break;
 658             case Resource::CSSStyleSheet:
 659                 stats.cssStyleSheets.addResource(resource);
 660                 break;
 661             case Resource::Script:
 662                 stats.scripts.addResource(resource);
 663                 break;
 664             case Resource::XSLStyleSheet:
 665                 stats.xslStyleSheets.addResource(resource);
 666                 break;
 667             case Resource::Font:
 668                 stats.fonts.addResource(resource);
 669                 break;
 670             default:
 671                 stats.other.addResource(resource);
 672                 break;
 673             }
 674         }
 675     }
 676     return stats;
 677 }
 678
 679 void MemoryCache::evictResources()
 680 {
 681     while (true) {
 682         ResourceMapIndex::iterator resourceMapIter = m_resourceMaps.begin();
 683         if (resourceMapIter == m_resourceMaps.end())
 684             break;
 685         ResourceMap* resources = resourceMapIter->value.get();
 686         while (true) {
 687             ResourceMap::iterator resourceIter = resources->begin();
 688             if (resourceIter == resources->end())
 689                 break;
 690             evict(resourceIter->value.get());
 691         }
 692         m_resourceMaps.remove(resourceMapIter);
 693     }
 694 }
 695
 696 void MemoryCache::prune(Resource* justReleasedResource)
 697 {
 698     TRACE_EVENT0("renderer", "MemoryCache::prune()");
 699
 700     if (m_inPruneResources)
 701         return;
 702     if (m_liveSize + m_deadSize <= m_capacity && m_maxDeadCapacity && m_deadSize <= m_maxDeadCapacity) // Fast path.
 703         return;
 704
 705     // To avoid burdening the current thread with repetitive pruning jobs,
 706     // pruning is postponed until the end of the current task. If it has
 707     // been more than m_maxPruneDeferralDelay since the last prune,
 708     // then we prune immediately.
 709     // If the current thread's run loop is not active, then pruning will happen
 710     // immediately only if it has been over m_maxPruneDeferralDelay
 711     // since the last prune.
 712     double currentTime = WTF::currentTime();
 713     if (m_prunePending) {
 714         if (currentTime - m_pruneTimeStamp >= m_maxPruneDeferralDelay) {
 715             pruneNow(currentTime, AutomaticPrune);
 716         }
 717     } else {
 718         if (currentTime - m_pruneTimeStamp >= m_maxPruneDeferralDelay) {
 719             pruneNow(currentTime, AutomaticPrune); // Delay exceeded, prune now.
 720         } else {
 721             // Defer.
 722             Platform::current()->currentThread()->addTaskObserver(this);
 723             m_prunePending = true;
 724         }
 725     }
 726
 727     if (m_prunePending && m_deadSize > m_maxDeferredPruneDeadCapacity && justReleasedResource) {
 728         // The following eviction does not respect LRU order, but it can be done
 729         // immediately in constant time, as opposed to pruneDeadResources, which
 730         // we would rather defer because it is O(N), which would make tear-down of N
 731         // objects O(N^2) if we pruned immediately. This immediate eviction is a
 732         // safeguard against runaway memory consumption by dead resources
 733         // while a prune is pending.
 734         // Main Resources in the cache are only substitue data that was
 735         // precached and should not be evicted.
 736         if (justReleasedResource->type() != Resource::MainResource) {
 737             if (MemoryCacheEntry* entry = getEntryForResource(justReleasedResource))
 738                 evict(entry);
 739         }
 740
 741         // As a last resort, prune immediately
 742         if (m_deadSize > m_maxDeferredPruneDeadCapacity)
 743             pruneNow(currentTime, AutomaticPrune);
 744     }
 745 }
 746
 747 void MemoryCache::willProcessTask()
 748 {
 749 }
 750
 751 void MemoryCache::didProcessTask()
 752 {
 753     // Perform deferred pruning
 754     ASSERT(m_prunePending);
 755     pruneNow(WTF::currentTime(), AutomaticPrune);
 756 }
 757
 758 void MemoryCache::pruneAll()
 759 {
 760     double currentTime = WTF::currentTime();
 761     pruneNow(currentTime, MaximalPrune);
 762 }
 763
 764 void MemoryCache::pruneNow(double currentTime, PruneStrategy strategy)
 765 {
 766     if (m_prunePending) {
 767         m_prunePending = false;
 768         Platform::current()->currentThread()->removeTaskObserver(this);
 769     }
 770
 771     TemporaryChange<bool> reentrancyProtector(m_inPruneResources, true);
 772     pruneDeadResources(strategy); // Prune dead first, in case it was "borrowing" capacity from live.
 773     pruneLiveResources(strategy);
 774     m_pruneFrameTimeStamp = m_lastFramePaintTimeStamp;
 775     m_pruneTimeStamp = currentTime;
 776 }
 777
 778 void MemoryCache::updateFramePaintTimestamp()
 779 {
 780     m_lastFramePaintTimeStamp = currentTime();
 781 }
 782
 783 void MemoryCache::registerLiveResource(Resource& resource)
 784 {
 785 #if ENABLE(OILPAN)
 786     ASSERT(!m_liveResources.contains(&resource));
 787     m_liveResources.add(&resource);
 788 #endif
 789 }
 790
 791 void MemoryCache::unregisterLiveResource(Resource& resource)
 792 {
 793 #if ENABLE(OILPAN)
 794     ASSERT(m_liveResources.contains(&resource));
 795     m_liveResources.remove(&resource);
 796 #endif
 797 }
 798
 799 #ifdef MEMORY_CACHE_STATS
 800
 801 void MemoryCache::dumpStats(Timer<MemoryCache>*)
 802 {
 803     Statistics s = getStatistics();
 804     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s\n", "", "Count", "Size", "LiveSize", "DecodedSize", "PurgeableSize", "PurgedSize");
 805     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s\n", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------");
 806     printf("%-13s %13d %13d %13d %13d %13d %13d\n", "Images", s.images.count, s.images.size, s.images.liveSize, s.images.decodedSize, s.images.purgeableSize, s.images.purgedSize);
 807     printf("%-13s %13d %13d %13d %13d %13d %13d\n", "CSS", s.cssStyleSheets.count, s.cssStyleSheets.size, s.cssStyleSheets.liveSize, s.cssStyleSheets.decodedSize, s.cssStyleSheets.purgeableSize, s.cssStyleSheets.purgedSize);
 808     printf("%-13s %13d %13d %13d %13d %13d %13d\n", "XSL", s.xslStyleSheets.count, s.xslStyleSheets.size, s.xslStyleSheets.liveSize, s.xslStyleSheets.decodedSize, s.xslStyleSheets.purgeableSize, s.xslStyleSheets.purgedSize);
 809     printf("%-13s %13d %13d %13d %13d %13d %13d\n", "JavaScript", s.scripts.count, s.scripts.size, s.scripts.liveSize, s.scripts.decodedSize, s.scripts.purgeableSize, s.scripts.purgedSize);
 810     printf("%-13s %13d %13d %13d %13d %13d %13d\n", "Fonts", s.fonts.count, s.fonts.size, s.fonts.liveSize, s.fonts.decodedSize, s.fonts.purgeableSize, s.fonts.purgedSize);
 811     printf("%-13s %13d %13d %13d %13d %13d %13d\n", "Other", s.other.count, s.other.size, s.other.liveSize, s.other.decodedSize, s.other.purgeableSize, s.other.purgedSize);
 812     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s\n\n", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------");
 813
 814     printf("Duplication of encoded data from data URLs\n");
 815     printf("%-13s %13d of %13d\n", "Images",     s.images.encodedSizeDuplicatedInDataURLs,         s.images.encodedSize);
 816     printf("%-13s %13d of %13d\n", "CSS",        s.cssStyleSheets.encodedSizeDuplicatedInDataURLs, s.cssStyleSheets.encodedSize);
 817     printf("%-13s %13d of %13d\n", "XSL",        s.xslStyleSheets.encodedSizeDuplicatedInDataURLs, s.xslStyleSheets.encodedSize);
 818     printf("%-13s %13d of %13d\n", "JavaScript", s.scripts.encodedSizeDuplicatedInDataURLs,        s.scripts.encodedSize);
 819     printf("%-13s %13d of %13d\n", "Fonts",      s.fonts.encodedSizeDuplicatedInDataURLs,          s.fonts.encodedSize);
 820     printf("%-13s %13d of %13d\n", "Other",      s.other.encodedSizeDuplicatedInDataURLs,          s.other.encodedSize);
 821 }
 822
 823 void MemoryCache::dumpLRULists(bool includeLive) const
 824 {
 825     printf("LRU-SP lists in eviction order (Kilobytes decoded, Kilobytes encoded, Access count, Referenced, isPurgeable, wasPurged):\n");
 826
 827     int size = m_allResources.size();
 828     for (int i = size - 1; i >= 0; i--) {
 829         printf("\n\nList %d: ", i);
 830         MemoryCacheEntry* current = m_allResources[i].m_tail;
 831         while (current) {
 832             ResourcePtr<Resource> currentResource = current->m_resource;
 833             if (includeLive || !currentResource->hasClients())
 834                 printf("(%.1fK, %.1fK, %uA, %dR, %d, %d); ", currentResource->decodedSize() / 1024.0f, (currentResource->encodedSize() + currentResource->overheadSize()) / 1024.0f, current->m_accessCount, currentResource->hasClients(), currentResource->isPurgeable(), currentResource->wasPurged());
 835
 836             current = current->m_previousInAllResourcesList;
 837         }
 838     }
 839 }
 840
 841 #endif // MEMORY_CACHE_STATS
 842
 843 } // namespace blink