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