928d2eee07dd77b3d922d4172a2135c24ce0e09f
[WebKit-https.git] / Source / WebCore / loader / cache / 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 "MemoryCache.h"
25
26 #include "BitmapImage.h"
27 #include "CachedImage.h"
28 #include "CachedImageClient.h"
29 #include "CachedResource.h"
30 #include "CachedResourceHandle.h"
31 #include "CrossThreadTask.h"
32 #include "Document.h"
33 #include "FrameLoader.h"
34 #include "FrameLoaderTypes.h"
35 #include "FrameView.h"
36 #include "Image.h"
37 #include "Logging.h"
38 #include "PublicSuffix.h"
39 #include "SecurityOrigin.h"
40 #include "SecurityOriginHash.h"
41 #include "WorkerGlobalScope.h"
42 #include "WorkerLoaderProxy.h"
43 #include "WorkerThread.h"
44 #include <stdio.h>
45 #include <wtf/CurrentTime.h>
46 #include <wtf/MathExtras.h>
47 #include <wtf/NeverDestroyed.h>
48 #include <wtf/TemporaryChange.h>
49 #include <wtf/text/CString.h>
50
51 #if ENABLE(DISK_IMAGE_CACHE)
52 #include "DiskImageCacheIOS.h"
53 #include "ResourceBuffer.h"
54 #endif
55
56 namespace WebCore {
57
58 static const int cDefaultCacheCapacity = 8192 * 1024;
59 static const double cMinDelayBeforeLiveDecodedPrune = 1; // Seconds.
60 static const float cTargetPrunePercentage = .95f; // Percentage of capacity toward which we prune, to avoid immediately pruning again.
61 static const double cDefaultDecodedDataDeletionInterval = 0;
62
63 MemoryCache* memoryCache()
64 {
65     static MemoryCache* staticCache = new MemoryCache;
66     ASSERT(WTF::isMainThread());
67
68     return staticCache;
69 }
70
71 MemoryCache::MemoryCache()
72     : m_disabled(false)
73     , m_pruneEnabled(true)
74     , m_inPruneResources(false)
75     , m_capacity(cDefaultCacheCapacity)
76     , m_minDeadCapacity(0)
77     , m_maxDeadCapacity(cDefaultCacheCapacity)
78     , m_deadDecodedDataDeletionInterval(cDefaultDecodedDataDeletionInterval)
79     , m_liveSize(0)
80     , m_deadSize(0)
81 {
82 }
83
84 MemoryCache::CachedResourceMap& MemoryCache::getSessionMap(SessionID sessionID)
85 {
86     ASSERT(sessionID.isValid());
87     CachedResourceMap* map = m_sessionResources.get(sessionID);
88     if (!map) {
89         m_sessionResources.set(sessionID, std::make_unique<CachedResourceMap>());
90         map = m_sessionResources.get(sessionID);
91     }
92     return *map;
93 }
94
95 URL MemoryCache::removeFragmentIdentifierIfNeeded(const URL& originalURL)
96 {
97     if (!originalURL.hasFragmentIdentifier())
98         return originalURL;
99     // Strip away fragment identifier from HTTP URLs.
100     // Data URLs must be unmodified. For file and custom URLs clients may expect resources 
101     // to be unique even when they differ by the fragment identifier only.
102     if (!originalURL.protocolIsInHTTPFamily())
103         return originalURL;
104     URL url = originalURL;
105     url.removeFragmentIdentifier();
106     return url;
107 }
108
109 bool MemoryCache::add(CachedResource* resource)
110 {
111     if (disabled())
112         return false;
113
114     ASSERT(WTF::isMainThread());
115
116     CachedResourceMap& resources = getSessionMap(resource->sessionID());
117 #if ENABLE(CACHE_PARTITIONING)
118     CachedResourceItem* originMap = resources.get(resource->url());
119     if (!originMap) {
120         originMap = new CachedResourceItem;
121         resources.set(resource->url(), adoptPtr(originMap));
122     }
123     originMap->set(resource->cachePartition(), resource);
124 #else
125     resources.set(resource->url(), resource);
126 #endif
127     resource->setInCache(true);
128     
129     resourceAccessed(resource);
130     
131     LOG(ResourceLoading, "MemoryCache::add Added '%s', resource %p\n", resource->url().string().latin1().data(), resource);
132     return true;
133 }
134
135 void MemoryCache::revalidationSucceeded(CachedResource* revalidatingResource, const ResourceResponse& response)
136 {
137     CachedResource* resource = revalidatingResource->resourceToRevalidate();
138     ASSERT(resource);
139     ASSERT(!resource->inCache());
140     ASSERT(resource->isLoaded());
141     ASSERT(revalidatingResource->inCache());
142
143     // Calling evict() can potentially delete revalidatingResource, which we use
144     // below. This mustn't be the case since revalidation means it is loaded
145     // and so canDelete() is false.
146     ASSERT(!revalidatingResource->canDelete());
147
148     evict(revalidatingResource);
149
150     CachedResourceMap& resources = getSessionMap(resource->sessionID());
151 #if ENABLE(CACHE_PARTITIONING)
152     ASSERT(!resources.get(resource->url()) || !resources.get(resource->url())->get(resource->cachePartition()));
153     CachedResourceItem* originMap = resources.get(resource->url());
154     if (!originMap) {
155         originMap = new CachedResourceItem;
156         resources.set(resource->url(), adoptPtr(originMap));
157     }
158     originMap->set(resource->cachePartition(), resource);
159 #else
160     ASSERT(!resources.get(resource->url()));
161     resources.set(resource->url(), resource);
162 #endif
163     resource->setInCache(true);
164     resource->updateResponseAfterRevalidation(response);
165     insertInLRUList(resource);
166     int delta = resource->size();
167     if (resource->decodedSize() && resource->hasClients())
168         insertInLiveDecodedResourcesList(resource);
169     if (delta)
170         adjustSize(resource->hasClients(), delta);
171     
172     revalidatingResource->switchClientsToRevalidatedResource();
173     ASSERT(!revalidatingResource->m_deleted);
174     // this deletes the revalidating resource
175     revalidatingResource->clearResourceToRevalidate();
176 }
177
178 void MemoryCache::revalidationFailed(CachedResource* revalidatingResource)
179 {
180     ASSERT(WTF::isMainThread());
181     LOG(ResourceLoading, "Revalidation failed for %p", revalidatingResource);
182     ASSERT(revalidatingResource->resourceToRevalidate());
183     revalidatingResource->clearResourceToRevalidate();
184 }
185
186 CachedResource* MemoryCache::resourceForURL(const URL& resourceURL)
187 {
188     return resourceForURL(resourceURL, SessionID::defaultSessionID());
189 }
190
191 CachedResource* MemoryCache::resourceForURL(const URL& resourceURL, SessionID sessionID)
192 {
193     return resourceForRequest(ResourceRequest(resourceURL), sessionID);
194 }
195
196 CachedResource* MemoryCache::resourceForRequest(const ResourceRequest& request, SessionID sessionID)
197 {
198     return resourceForRequestImpl(request, getSessionMap(sessionID));
199 }
200
201 CachedResource* MemoryCache::resourceForRequestImpl(const ResourceRequest& request, CachedResourceMap& resources)
202 {
203     ASSERT(WTF::isMainThread());
204     URL url = removeFragmentIdentifierIfNeeded(request.url());
205
206 #if ENABLE(CACHE_PARTITIONING)
207     CachedResourceItem* item = resources.get(url);
208     CachedResource* resource = 0;
209     if (item)
210         resource = item->get(request.cachePartition());
211 #else
212     CachedResource* resource = resources.get(url);
213 #endif
214     bool wasPurgeable = MemoryCache::shouldMakeResourcePurgeableOnEviction() && resource && resource->isPurgeable();
215     if (resource && !resource->makePurgeable(false)) {
216         ASSERT(!resource->hasClients());
217         evict(resource);
218         return 0;
219     }
220     // Add the size back since we had subtracted it when we marked the memory as purgeable.
221     if (wasPurgeable)
222         adjustSize(resource->hasClients(), resource->size());
223     return resource;
224 }
225
226 unsigned MemoryCache::deadCapacity() const 
227 {
228     // Dead resource capacity is whatever space is not occupied by live resources, bounded by an independent minimum and maximum.
229     unsigned capacity = m_capacity - std::min(m_liveSize, m_capacity); // Start with available capacity.
230     capacity = std::max(capacity, m_minDeadCapacity); // Make sure it's above the minimum.
231     capacity = std::min(capacity, m_maxDeadCapacity); // Make sure it's below the maximum.
232     return capacity;
233 }
234
235 unsigned MemoryCache::liveCapacity() const 
236
237     // Live resource capacity is whatever is left over after calculating dead resource capacity.
238     return m_capacity - deadCapacity();
239 }
240
241 #if USE(CG)
242 // FIXME: Remove the USE(CG) once we either make NativeImagePtr a smart pointer on all platforms or
243 // remove the usage of CFRetain() in MemoryCache::addImageToCache() so as to make the code platform-independent.
244 static CachedImageClient& dummyCachedImageClient()
245 {
246     static NeverDestroyed<CachedImageClient> client;
247     return client;
248 }
249
250 bool MemoryCache::addImageToCache(NativeImagePtr image, const URL& url, const String& cachePartition)
251 {
252     ASSERT(image);
253     SessionID sessionID = SessionID::defaultSessionID();
254     removeImageFromCache(url, cachePartition); // Remove cache entry if it already exists.
255
256     RefPtr<BitmapImage> bitmapImage = BitmapImage::create(image, nullptr);
257     if (!bitmapImage)
258         return false;
259
260     std::unique_ptr<CachedImage> cachedImage = std::make_unique<CachedImage>(url, bitmapImage.get(), CachedImage::ManuallyCached, sessionID);
261
262     // Actual release of the CGImageRef is done in BitmapImage.
263     CFRetain(image);
264     cachedImage->addClient(&dummyCachedImageClient());
265     cachedImage->setDecodedSize(bitmapImage->decodedSize());
266 #if ENABLE(CACHE_PARTITIONING)
267     cachedImage->resourceRequest().setCachePartition(cachePartition);
268 #endif
269     return add(cachedImage.release());
270 }
271
272 void MemoryCache::removeImageFromCache(const URL& url, const String& cachePartition)
273 {
274     CachedResourceMap& resources = getSessionMap(SessionID::defaultSessionID());
275 #if ENABLE(CACHE_PARTITIONING)
276     CachedResource* resource;
277     if (CachedResourceItem* item = resources.get(url))
278         resource = item->get(ResourceRequest::partitionName(cachePartition));
279     else
280         resource = nullptr;
281 #else
282     UNUSED_PARAM(cachePartition);
283     CachedResource* resource = resources.get(url);
284 #endif
285     if (!resource)
286         return;
287
288     // A resource exists and is not a manually cached image, so just remove it.
289     if (!resource->isImage() || !toCachedImage(resource)->isManuallyCached()) {
290         evict(resource);
291         return;
292     }
293
294     // Removing the last client of a CachedImage turns the resource
295     // into a dead resource which will eventually be evicted when
296     // dead resources are pruned. That might be immediately since
297     // removing the last client triggers a MemoryCache::prune, so the
298     // resource may be deleted after this call.
299     toCachedImage(resource)->removeClient(&dummyCachedImageClient());
300 }
301 #endif
302
303 void MemoryCache::pruneLiveResources(bool shouldDestroyDecodedDataForAllLiveResources)
304 {
305     if (!m_pruneEnabled)
306         return;
307
308     unsigned capacity = shouldDestroyDecodedDataForAllLiveResources ? 0 : liveCapacity();
309     if (capacity && m_liveSize <= capacity)
310         return;
311
312     unsigned targetSize = static_cast<unsigned>(capacity * cTargetPrunePercentage); // Cut by a percentage to avoid immediately pruning again.
313
314     pruneLiveResourcesToSize(targetSize, shouldDestroyDecodedDataForAllLiveResources);
315 }
316
317 void MemoryCache::pruneLiveResourcesToPercentage(float prunePercentage)
318 {
319     if (!m_pruneEnabled)
320         return;
321
322     if (prunePercentage < 0.0f  || prunePercentage > 0.95f)
323         return;
324
325     unsigned currentSize = m_liveSize + m_deadSize;
326     unsigned targetSize = static_cast<unsigned>(currentSize * prunePercentage);
327
328     pruneLiveResourcesToSize(targetSize);
329 }
330
331 void MemoryCache::pruneLiveResourcesToSize(unsigned targetSize, bool shouldDestroyDecodedDataForAllLiveResources)
332 {
333     if (m_inPruneResources)
334         return;
335     TemporaryChange<bool> reentrancyProtector(m_inPruneResources, true);
336
337     double currentTime = FrameView::currentPaintTimeStamp();
338     if (!currentTime) // In case prune is called directly, outside of a Frame paint.
339         currentTime = monotonicallyIncreasingTime();
340     
341     // Destroy any decoded data in live objects that we can.
342     // Start from the tail, since this is the least recently accessed of the objects.
343
344     // The list might not be sorted by the m_lastDecodedAccessTime. The impact
345     // of this weaker invariant is minor as the below if statement to check the
346     // elapsedTime will evaluate to false as the currentTime will be a lot
347     // greater than the current->m_lastDecodedAccessTime.
348     // For more details see: https://bugs.webkit.org/show_bug.cgi?id=30209
349     CachedResource* current = m_liveDecodedResources.m_tail;
350     while (current) {
351         CachedResource* prev = current->m_prevInLiveResourcesList;
352         ASSERT(current->hasClients());
353         if (current->isLoaded() && current->decodedSize()) {
354             // Check to see if the remaining resources are too new to prune.
355             double elapsedTime = currentTime - current->m_lastDecodedAccessTime;
356             if (!shouldDestroyDecodedDataForAllLiveResources && elapsedTime < cMinDelayBeforeLiveDecodedPrune)
357                 return;
358
359             // Destroy our decoded data. This will remove us from 
360             // m_liveDecodedResources, and possibly move us to a different LRU 
361             // list in m_allResources.
362             current->destroyDecodedData();
363
364             if (targetSize && m_liveSize <= targetSize)
365                 return;
366         }
367         current = prev;
368     }
369 }
370
371 void MemoryCache::pruneDeadResources()
372 {
373     if (!m_pruneEnabled)
374         return;
375
376     unsigned capacity = deadCapacity();
377     if (capacity && m_deadSize <= capacity)
378         return;
379
380     unsigned targetSize = static_cast<unsigned>(capacity * cTargetPrunePercentage); // Cut by a percentage to avoid immediately pruning again.
381     pruneDeadResourcesToSize(targetSize);
382 }
383
384 void MemoryCache::pruneDeadResourcesToPercentage(float prunePercentage)
385 {
386     if (!m_pruneEnabled)
387         return;
388
389     if (prunePercentage < 0.0f  || prunePercentage > 0.95f)
390         return;
391
392     unsigned currentSize = m_liveSize + m_deadSize;
393     unsigned targetSize = static_cast<unsigned>(currentSize * prunePercentage);
394
395     pruneDeadResourcesToSize(targetSize);
396 }
397
398 void MemoryCache::pruneDeadResourcesToSize(unsigned targetSize)
399 {
400     if (m_inPruneResources)
401         return;
402     TemporaryChange<bool> reentrancyProtector(m_inPruneResources, true);
403
404     int size = m_allResources.size();
405  
406     // See if we have any purged resources we can evict.
407     for (int i = 0; i < size; i++) {
408         CachedResource* current = m_allResources[i].m_tail;
409         while (current) {
410             CachedResource* prev = current->m_prevInAllResourcesList;
411             if (current->wasPurged()) {
412                 ASSERT(!current->hasClients());
413                 ASSERT(!current->isPreloaded());
414                 evict(current);
415             }
416             current = prev;
417         }
418     }
419     if (targetSize && m_deadSize <= targetSize)
420         return;
421
422     bool canShrinkLRULists = true;
423     for (int i = size - 1; i >= 0; i--) {
424         // Remove from the tail, since this is the least frequently accessed of the objects.
425         CachedResource* current = m_allResources[i].m_tail;
426         
427         // First flush all the decoded data in this queue.
428         while (current) {
429             // Protect 'previous' so it can't get deleted during destroyDecodedData().
430             CachedResourceHandle<CachedResource> previous = current->m_prevInAllResourcesList;
431             ASSERT(!previous || previous->inCache());
432             if (!current->hasClients() && !current->isPreloaded() && current->isLoaded()) {
433                 // Destroy our decoded data. This will remove us from 
434                 // m_liveDecodedResources, and possibly move us to a different 
435                 // LRU list in m_allResources.
436                 current->destroyDecodedData();
437
438                 if (targetSize && m_deadSize <= targetSize)
439                     return;
440             }
441             // Decoded data may reference other resources. Stop iterating if 'previous' somehow got
442             // kicked out of cache during destroyDecodedData().
443             if (previous && !previous->inCache())
444                 break;
445             current = previous.get();
446         }
447
448         // Now evict objects from this queue.
449         current = m_allResources[i].m_tail;
450         while (current) {
451             CachedResourceHandle<CachedResource> previous = current->m_prevInAllResourcesList;
452             ASSERT(!previous || previous->inCache());
453             if (!current->hasClients() && !current->isPreloaded() && !current->isCacheValidator()) {
454                 if (!makeResourcePurgeable(current))
455                     evict(current);
456
457                 if (targetSize && m_deadSize <= targetSize)
458                     return;
459             }
460             if (previous && !previous->inCache())
461                 break;
462             current = previous.get();
463         }
464             
465         // Shrink the vector back down so we don't waste time inspecting
466         // empty LRU lists on future prunes.
467         if (m_allResources[i].m_head)
468             canShrinkLRULists = false;
469         else if (canShrinkLRULists)
470             m_allResources.resize(i);
471     }
472 }
473
474 #if ENABLE(DISK_IMAGE_CACHE)
475 void MemoryCache::flushCachedImagesToDisk()
476 {
477     if (!diskImageCache().isEnabled())
478         return;
479
480 #ifndef NDEBUG
481     double start = WTF::currentTimeMS();
482     unsigned resourceCount = 0;
483     unsigned cachedSize = 0;
484 #endif
485
486     for (size_t i = m_allResources.size(); i; ) {
487         --i;
488         CachedResource* current = m_allResources[i].m_tail;
489         while (current) {
490             CachedResource* previous = current->m_prevInAllResourcesList;
491
492             if (!current->isUsingDiskImageCache() && current->canUseDiskImageCache()) {
493                 current->useDiskImageCache();
494                 current->destroyDecodedData();
495 #ifndef NDEBUG
496                 LOG(DiskImageCache, "Cache::diskCacheResources(): attempting to save (%d) bytes", current->resourceBuffer()->sharedBuffer()->size());
497                 ++resourceCount;
498                 cachedSize += current->resourceBuffer()->sharedBuffer()->size();
499 #endif
500             }
501
502             current = previous;
503         }
504     }
505
506 #ifndef NDEBUG
507     double end = WTF::currentTimeMS();
508     LOG(DiskImageCache, "DiskImageCache: took (%f) ms to cache (%d) bytes for (%d) resources", end - start, cachedSize, resourceCount);
509 #endif
510 }
511 #endif // ENABLE(DISK_IMAGE_CACHE)
512
513 void MemoryCache::setCapacities(unsigned minDeadBytes, unsigned maxDeadBytes, unsigned totalBytes)
514 {
515     ASSERT(minDeadBytes <= maxDeadBytes);
516     ASSERT(maxDeadBytes <= totalBytes);
517     m_minDeadCapacity = minDeadBytes;
518     m_maxDeadCapacity = maxDeadBytes;
519     m_capacity = totalBytes;
520     prune();
521 }
522
523 bool MemoryCache::makeResourcePurgeable(CachedResource* resource)
524 {
525     if (!MemoryCache::shouldMakeResourcePurgeableOnEviction())
526         return false;
527
528     if (!resource->inCache())
529         return false;
530
531     if (resource->isPurgeable())
532         return true;
533
534     if (!resource->isSafeToMakePurgeable())
535         return false;
536
537     if (!resource->makePurgeable(true))
538         return false;
539
540     adjustSize(resource->hasClients(), -static_cast<int>(resource->size()));
541
542     return true;
543 }
544
545 void MemoryCache::evict(CachedResource* resource)
546 {
547     ASSERT(WTF::isMainThread());
548     LOG(ResourceLoading, "Evicting resource %p for '%s' from cache", resource, resource->url().string().latin1().data());
549     // The resource may have already been removed by someone other than our caller,
550     // who needed a fresh copy for a reload. See <http://bugs.webkit.org/show_bug.cgi?id=12479#c6>.
551     CachedResourceMap& resources = getSessionMap(resource->sessionID());
552     if (resource->inCache()) {
553         // Remove from the resource map.
554 #if ENABLE(CACHE_PARTITIONING)
555         CachedResourceItem* item = resources.get(resource->url());
556         if (item) {
557             item->remove(resource->cachePartition());
558             if (!item->size())
559                 resources.remove(resource->url());
560         }
561 #else
562         resources.remove(resource->url());
563 #endif
564         resource->setInCache(false);
565
566         // Remove from the appropriate LRU list.
567         removeFromLRUList(resource);
568         removeFromLiveDecodedResourcesList(resource);
569
570         // If the resource was purged, it means we had already decremented the size when we made the
571         // resource purgeable in makeResourcePurgeable(). So adjust the size if we are evicting a
572         // resource that was not marked as purgeable.
573         if (!MemoryCache::shouldMakeResourcePurgeableOnEviction() || !resource->isPurgeable())
574             adjustSize(resource->hasClients(), -static_cast<int>(resource->size()));
575     } else
576 #if ENABLE(CACHE_PARTITIONING)
577         ASSERT(!resources.get(resource->url()) || resources.get(resource->url())->get(resource->cachePartition()) != resource);
578 #else
579         ASSERT(resources.get(resource->url()) != resource);
580 #endif
581
582     resource->deleteIfPossible();
583 }
584
585 MemoryCache::LRUList* MemoryCache::lruListFor(CachedResource* resource)
586 {
587     unsigned accessCount = std::max(resource->accessCount(), 1U);
588     unsigned queueIndex = WTF::fastLog2(resource->size() / accessCount);
589 #ifndef NDEBUG
590     resource->m_lruIndex = queueIndex;
591 #endif
592     if (m_allResources.size() <= queueIndex)
593         m_allResources.grow(queueIndex + 1);
594     return &m_allResources[queueIndex];
595 }
596
597 void MemoryCache::removeFromLRUList(CachedResource* resource)
598 {
599     // If we've never been accessed, then we're brand new and not in any list.
600     if (resource->accessCount() == 0)
601         return;
602
603 #if !ASSERT_DISABLED
604     unsigned oldListIndex = resource->m_lruIndex;
605 #endif
606
607     LRUList* list = lruListFor(resource);
608
609 #if !ASSERT_DISABLED
610     // Verify that the list we got is the list we want.
611     ASSERT(resource->m_lruIndex == oldListIndex);
612
613     // Verify that we are in fact in this list.
614     bool found = false;
615     for (CachedResource* current = list->m_head; current; current = current->m_nextInAllResourcesList) {
616         if (current == resource) {
617             found = true;
618             break;
619         }
620     }
621     ASSERT(found);
622 #endif
623
624     CachedResource* next = resource->m_nextInAllResourcesList;
625     CachedResource* prev = resource->m_prevInAllResourcesList;
626     
627     if (next == 0 && prev == 0 && list->m_head != resource)
628         return;
629     
630     resource->m_nextInAllResourcesList = 0;
631     resource->m_prevInAllResourcesList = 0;
632     
633     if (next)
634         next->m_prevInAllResourcesList = prev;
635     else if (list->m_tail == resource)
636         list->m_tail = prev;
637
638     if (prev)
639         prev->m_nextInAllResourcesList = next;
640     else if (list->m_head == resource)
641         list->m_head = next;
642 }
643
644 void MemoryCache::insertInLRUList(CachedResource* resource)
645 {
646     // Make sure we aren't in some list already.
647     ASSERT(!resource->m_nextInAllResourcesList && !resource->m_prevInAllResourcesList);
648     ASSERT(resource->inCache());
649     ASSERT(resource->accessCount() > 0);
650     
651     LRUList* list = lruListFor(resource);
652
653     resource->m_nextInAllResourcesList = list->m_head;
654     if (list->m_head)
655         list->m_head->m_prevInAllResourcesList = resource;
656     list->m_head = resource;
657     
658     if (!resource->m_nextInAllResourcesList)
659         list->m_tail = resource;
660         
661 #if !ASSERT_DISABLED
662     // Verify that we are in now in the list like we should be.
663     list = lruListFor(resource);
664     bool found = false;
665     for (CachedResource* current = list->m_head; current; current = current->m_nextInAllResourcesList) {
666         if (current == resource) {
667             found = true;
668             break;
669         }
670     }
671     ASSERT(found);
672 #endif
673
674 }
675
676 void MemoryCache::resourceAccessed(CachedResource* resource)
677 {
678     ASSERT(resource->inCache());
679     
680     // Need to make sure to remove before we increase the access count, since
681     // the queue will possibly change.
682     removeFromLRUList(resource);
683     
684     // If this is the first time the resource has been accessed, adjust the size of the cache to account for its initial size.
685     if (!resource->accessCount())
686         adjustSize(resource->hasClients(), resource->size());
687     
688     // Add to our access count.
689     resource->increaseAccessCount();
690     
691     // Now insert into the new queue.
692     insertInLRUList(resource);
693 }
694
695 void MemoryCache::removeResourcesWithOrigin(SecurityOrigin* origin)
696 {
697     Vector<CachedResource*> resourcesWithOrigin;
698
699     for (auto& resources : m_sessionResources) {
700         CachedResourceMap::iterator e = resources.value->end();
701 #if ENABLE(CACHE_PARTITIONING)
702         String originPartition = ResourceRequest::partitionName(origin->host());
703 #endif
704
705         for (CachedResourceMap::iterator it = resources.value->begin(); it != e; ++it) {
706 #if ENABLE(CACHE_PARTITIONING)
707             for (CachedResourceItem::iterator itemIterator = it->value->begin(); itemIterator != it->value->end(); ++itemIterator) {
708                 CachedResource* resource = itemIterator->value;
709                 String partition = itemIterator->key;
710                 if (partition == originPartition) {
711                     resourcesWithOrigin.append(resource);
712                     continue;
713                 }
714 #else
715                 CachedResource* resource = it->value;
716 #endif
717                 RefPtr<SecurityOrigin> resourceOrigin = SecurityOrigin::createFromString(resource->url());
718                 if (!resourceOrigin)
719                     continue;
720                 if (resourceOrigin->equal(origin))
721                     resourcesWithOrigin.append(resource);
722 #if ENABLE(CACHE_PARTITIONING)
723             }
724 #endif
725         }
726     }
727
728     for (size_t i = 0; i < resourcesWithOrigin.size(); ++i)
729         remove(resourcesWithOrigin[i]);
730 }
731
732 void MemoryCache::getOriginsWithCache(SecurityOriginSet& origins)
733 {
734 #if ENABLE(CACHE_PARTITIONING)
735     DEPRECATED_DEFINE_STATIC_LOCAL(String, httpString, ("http"));
736 #endif
737     for (auto& resources : m_sessionResources) {
738         CachedResourceMap::iterator e = resources.value->end();
739         for (CachedResourceMap::iterator it = resources.value->begin(); it != e; ++it) {
740 #if ENABLE(CACHE_PARTITIONING)
741             if (it->value->begin()->key == emptyString())
742                 origins.add(SecurityOrigin::createFromString(it->value->begin()->value->url()));
743             else
744                 origins.add(SecurityOrigin::create(httpString, it->value->begin()->key, 0));
745 #else
746             origins.add(SecurityOrigin::createFromString(it->value->url()));
747 #endif
748         }
749     }
750 }
751
752 void MemoryCache::removeFromLiveDecodedResourcesList(CachedResource* resource)
753 {
754     // If we've never been accessed, then we're brand new and not in any list.
755     if (!resource->m_inLiveDecodedResourcesList)
756         return;
757     resource->m_inLiveDecodedResourcesList = false;
758
759 #if !ASSERT_DISABLED
760     // Verify that we are in fact in this list.
761     bool found = false;
762     for (CachedResource* current = m_liveDecodedResources.m_head; current; current = current->m_nextInLiveResourcesList) {
763         if (current == resource) {
764             found = true;
765             break;
766         }
767     }
768     ASSERT(found);
769 #endif
770
771     CachedResource* next = resource->m_nextInLiveResourcesList;
772     CachedResource* prev = resource->m_prevInLiveResourcesList;
773     
774     if (next == 0 && prev == 0 && m_liveDecodedResources.m_head != resource)
775         return;
776     
777     resource->m_nextInLiveResourcesList = 0;
778     resource->m_prevInLiveResourcesList = 0;
779     
780     if (next)
781         next->m_prevInLiveResourcesList = prev;
782     else if (m_liveDecodedResources.m_tail == resource)
783         m_liveDecodedResources.m_tail = prev;
784
785     if (prev)
786         prev->m_nextInLiveResourcesList = next;
787     else if (m_liveDecodedResources.m_head == resource)
788         m_liveDecodedResources.m_head = next;
789 }
790
791 void MemoryCache::insertInLiveDecodedResourcesList(CachedResource* resource)
792 {
793     // Make sure we aren't in the list already.
794     ASSERT(!resource->m_nextInLiveResourcesList && !resource->m_prevInLiveResourcesList && !resource->m_inLiveDecodedResourcesList);
795     resource->m_inLiveDecodedResourcesList = true;
796
797     resource->m_nextInLiveResourcesList = m_liveDecodedResources.m_head;
798     if (m_liveDecodedResources.m_head)
799         m_liveDecodedResources.m_head->m_prevInLiveResourcesList = resource;
800     m_liveDecodedResources.m_head = resource;
801     
802     if (!resource->m_nextInLiveResourcesList)
803         m_liveDecodedResources.m_tail = resource;
804         
805 #if !ASSERT_DISABLED
806     // Verify that we are in now in the list like we should be.
807     bool found = false;
808     for (CachedResource* current = m_liveDecodedResources.m_head; current; current = current->m_nextInLiveResourcesList) {
809         if (current == resource) {
810             found = true;
811             break;
812         }
813     }
814     ASSERT(found);
815 #endif
816
817 }
818
819 void MemoryCache::addToLiveResourcesSize(CachedResource* resource)
820 {
821     m_liveSize += resource->size();
822     m_deadSize -= resource->size();
823 }
824
825 void MemoryCache::removeFromLiveResourcesSize(CachedResource* resource)
826 {
827     m_liveSize -= resource->size();
828     m_deadSize += resource->size();
829 }
830
831 void MemoryCache::adjustSize(bool live, int delta)
832 {
833     if (live) {
834         ASSERT(delta >= 0 || ((int)m_liveSize + delta >= 0));
835         m_liveSize += delta;
836     } else {
837         ASSERT(delta >= 0 || ((int)m_deadSize + delta >= 0));
838         m_deadSize += delta;
839     }
840 }
841
842 void MemoryCache::removeUrlFromCache(ScriptExecutionContext* context, const String& urlString, SessionID sessionID)
843 {
844     removeRequestFromCache(context, ResourceRequest(urlString), sessionID);
845 }
846
847 void MemoryCache::removeRequestFromCache(ScriptExecutionContext* context, const ResourceRequest& request, SessionID sessionID)
848 {
849     if (context->isWorkerGlobalScope()) {
850         toWorkerGlobalScope(context)->thread().workerLoaderProxy().postTaskToLoader(CrossThreadTask(&crossThreadRemoveRequestFromCache, request, sessionID));
851         return;
852     }
853
854     removeRequestFromCacheImpl(context, request, sessionID);
855 }
856
857 void MemoryCache::removeRequestFromCacheImpl(ScriptExecutionContext*, const ResourceRequest& request, SessionID sessionID)
858 {
859     if (CachedResource* resource = memoryCache()->resourceForRequest(request, sessionID))
860         memoryCache()->remove(resource);
861 }
862
863 void MemoryCache::removeRequestFromSessionCaches(ScriptExecutionContext* context, const ResourceRequest& request)
864 {
865     if (context->isWorkerGlobalScope()) {
866         toWorkerGlobalScope(context)->thread().workerLoaderProxy().postTaskToLoader(CrossThreadTask(&crossThreadRemoveRequestFromSessionCaches, request));
867         return;
868     }
869     removeRequestFromSessionCachesImpl(context, request);
870 }
871
872 void MemoryCache::removeRequestFromSessionCachesImpl(ScriptExecutionContext*, const ResourceRequest& request)
873 {
874     for (auto& resources : memoryCache()->m_sessionResources) {
875         if (CachedResource* resource = memoryCache()->resourceForRequestImpl(request, *resources.value))
876         memoryCache()->remove(resource);
877     }
878 }
879
880 void MemoryCache::crossThreadRemoveRequestFromCache(ScriptExecutionContext* context, PassOwnPtr<WebCore::CrossThreadResourceRequestData> requestData, SessionID sessionID)
881 {
882     OwnPtr<ResourceRequest> request(ResourceRequest::adopt(requestData));
883     MemoryCache::removeRequestFromCacheImpl(context, *request, sessionID);
884 }
885
886 void MemoryCache::crossThreadRemoveRequestFromSessionCaches(ScriptExecutionContext* context, PassOwnPtr<WebCore::CrossThreadResourceRequestData> requestData)
887 {
888     OwnPtr<ResourceRequest> request(ResourceRequest::adopt(requestData));
889     MemoryCache::removeRequestFromSessionCaches(context, *request);
890 }
891
892 void MemoryCache::TypeStatistic::addResource(CachedResource* o)
893 {
894     bool purged = o->wasPurged();
895     bool purgeable = o->isPurgeable() && !purged; 
896     int pageSize = (o->encodedSize() + o->overheadSize() + 4095) & ~4095;
897     count++;
898     size += purged ? 0 : o->size(); 
899     liveSize += o->hasClients() ? o->size() : 0;
900     decodedSize += o->decodedSize();
901     purgeableSize += purgeable ? pageSize : 0;
902     purgedSize += purged ? pageSize : 0;
903 #if ENABLE(DISK_IMAGE_CACHE)
904     // Only the data inside the resource was mapped, not the entire resource.
905     mappedSize += o->isUsingDiskImageCache() ? o->resourceBuffer()->sharedBuffer()->size() : 0;
906 #endif
907 }
908
909 MemoryCache::Statistics MemoryCache::getStatistics()
910 {
911     Statistics stats;
912
913     for (auto& resources : m_sessionResources) {
914         CachedResourceMap::iterator e = resources.value->end();
915         for (CachedResourceMap::iterator i = resources.value->begin(); i != e; ++i) {
916 #if ENABLE(CACHE_PARTITIONING)
917             for (CachedResourceItem::iterator itemIterator = i->value->begin(); itemIterator != i->value->end(); ++itemIterator) {
918                 CachedResource* resource = itemIterator->value;
919 #else
920                 CachedResource* resource = i->value;
921 #endif
922                 switch (resource->type()) {
923                 case CachedResource::ImageResource:
924                     stats.images.addResource(resource);
925                     break;
926                 case CachedResource::CSSStyleSheet:
927                     stats.cssStyleSheets.addResource(resource);
928                     break;
929                 case CachedResource::Script:
930                     stats.scripts.addResource(resource);
931                     break;
932 #if ENABLE(XSLT)
933                 case CachedResource::XSLStyleSheet:
934                     stats.xslStyleSheets.addResource(resource);
935                     break;
936 #endif
937                 case CachedResource::FontResource:
938                     stats.fonts.addResource(resource);
939                     break;
940                 default:
941                     break;
942                 }
943 #if ENABLE(CACHE_PARTITIONING)
944             }
945 #endif
946         }
947     }
948     return stats;
949 }
950
951 void MemoryCache::setDisabled(bool disabled)
952 {
953     m_disabled = disabled;
954     if (!m_disabled)
955         return;
956
957     for (;;) {
958         SessionCachedResourceMap::iterator sessionIterator = m_sessionResources.begin();
959         if (sessionIterator == m_sessionResources.end())
960             break;
961         CachedResourceMap::iterator outerIterator = sessionIterator->value->begin();
962         if (outerIterator == sessionIterator->value->end())
963             break;
964 #if ENABLE(CACHE_PARTITIONING)
965         CachedResourceItem::iterator innerIterator = outerIterator->value->begin();
966         evict(innerIterator->value);
967 #else
968         evict(outerIterator->value);
969 #endif
970     }
971 }
972
973 void MemoryCache::evictResources()
974 {
975     if (disabled())
976         return;
977
978     setDisabled(true);
979     setDisabled(false);
980 }
981
982 void MemoryCache::prune()
983 {
984     if (m_liveSize + m_deadSize <= m_capacity && m_deadSize <= m_maxDeadCapacity) // Fast path.
985         return;
986         
987     pruneDeadResources(); // Prune dead first, in case it was "borrowing" capacity from live.
988     pruneLiveResources();
989 }
990
991 void MemoryCache::pruneToPercentage(float targetPercentLive)
992 {
993     pruneDeadResourcesToPercentage(targetPercentLive); // Prune dead first, in case it was "borrowing" capacity from live.
994     pruneLiveResourcesToPercentage(targetPercentLive);
995 }
996
997
998 #ifndef NDEBUG
999 void MemoryCache::dumpStats()
1000 {
1001     Statistics s = getStatistics();
1002 #if ENABLE(DISK_IMAGE_CACHE)
1003     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s %-13s %-13s\n", "", "Count", "Size", "LiveSize", "DecodedSize", "PurgeableSize", "PurgedSize", "Mapped", "\"Real\"");
1004     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s %-13s %-13s\n", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------");
1005     printf("%-13s %13d %13d %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, s.images.mappedSize, s.images.size - s.images.mappedSize);
1006 #else
1007     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s\n", "", "Count", "Size", "LiveSize", "DecodedSize", "PurgeableSize", "PurgedSize");
1008     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s\n", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------");
1009     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);
1010 #endif
1011     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);
1012 #if ENABLE(XSLT)
1013     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);
1014 #endif
1015     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);
1016     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);
1017     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s\n\n", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------");
1018 }
1019
1020 void MemoryCache::dumpLRULists(bool includeLive) const
1021 {
1022 #if ENABLE(DISK_IMAGE_CACHE)
1023     printf("LRU-SP lists in eviction order (Kilobytes decoded, Kilobytes encoded, Access count, Referenced, isPurgeable, wasPurged, isMemoryMapped):\n");
1024 #else
1025     printf("LRU-SP lists in eviction order (Kilobytes decoded, Kilobytes encoded, Access count, Referenced, isPurgeable, wasPurged):\n");
1026 #endif
1027
1028     int size = m_allResources.size();
1029     for (int i = size - 1; i >= 0; i--) {
1030         printf("\n\nList %d: ", i);
1031         CachedResource* current = m_allResources[i].m_tail;
1032         while (current) {
1033             CachedResource* prev = current->m_prevInAllResourcesList;
1034             if (includeLive || !current->hasClients())
1035 #if ENABLE(DISK_IMAGE_CACHE)
1036                 printf("(%.1fK, %.1fK, %uA, %dR, %d, %d, %d); ", current->decodedSize() / 1024.0f, (current->encodedSize() + current->overheadSize()) / 1024.0f, current->accessCount(), current->hasClients(), current->isPurgeable(), current->wasPurged(), current->isUsingDiskImageCache());
1037 #else
1038                 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());
1039 #endif
1040
1041             current = prev;
1042         }
1043     }
1044 }
1045 #endif
1046
1047 } // namespace WebCore