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
56namespace WebCore {
57
58static const int cDefaultCacheCapacity = 8192 * 1024;
59static const double cMinDelayBeforeLiveDecodedPrune = 1; // Seconds.
60static const float cTargetPrunePercentage = .95f; // Percentage of capacity toward which we prune, to avoid immediately pruning again.
61static const auto defaultDecodedDataDeletionInterval = std::chrono::seconds { 0 };
62
63MemoryCache* memoryCache()
64{
65    static MemoryCache* staticCache = new MemoryCache;
66    ASSERT(WTF::isMainThread());
67
68    return staticCache;
69}
70
71MemoryCache::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(defaultDecodedDataDeletionInterval)
79    , m_liveSize(0)
80    , m_deadSize(0)
81{
82}
83
84MemoryCache::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
95URL 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
109bool 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
135void 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
178void 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
186CachedResource* MemoryCache::resourceForURL(const URL& resourceURL)
187{
188    return resourceForURL(resourceURL, SessionID::defaultSessionID());
189}
190
191CachedResource* MemoryCache::resourceForURL(const URL& resourceURL, SessionID sessionID)
192{
193    return resourceForRequest(ResourceRequest(resourceURL), sessionID);
194}
195
196CachedResource* MemoryCache::resourceForRequest(const ResourceRequest& request, SessionID sessionID)
197{
198    return resourceForRequestImpl(request, getSessionMap(sessionID));
199}
200
201CachedResource* 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
226unsigned 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
235unsigned 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.
244static CachedImageClient& dummyCachedImageClient()
245{
246    static NeverDestroyed<CachedImageClient> client;
247    return client;
248}
249
250bool 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
272void 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
303void 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
317void 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
331void 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
371void 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
384void 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
398void 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)
475void 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
513void 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
523bool 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
545void 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
585MemoryCache::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
597void 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
644void 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
676void 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
695void 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
732void 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
752void 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
791void 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
819void MemoryCache::addToLiveResourcesSize(CachedResource* resource)
820{
821    m_liveSize += resource->size();
822    m_deadSize -= resource->size();
823}
824
825void MemoryCache::removeFromLiveResourcesSize(CachedResource* resource)
826{
827    m_liveSize -= resource->size();
828    m_deadSize += resource->size();
829}
830
831void 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
842void MemoryCache::removeUrlFromCache(ScriptExecutionContext* context, const String& urlString, SessionID sessionID)
843{
844    removeRequestFromCache(context, ResourceRequest(urlString), sessionID);
845}
846
847void 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
857void MemoryCache::removeRequestFromCacheImpl(ScriptExecutionContext*, const ResourceRequest& request, SessionID sessionID)
858{
859    if (CachedResource* resource = memoryCache()->resourceForRequest(request, sessionID))
860        memoryCache()->remove(resource);
861}
862
863void 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
872void 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
880void 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
886void MemoryCache::crossThreadRemoveRequestFromSessionCaches(ScriptExecutionContext& context, PassOwnPtr<WebCore::CrossThreadResourceRequestData> requestData)
887{
888    OwnPtr<ResourceRequest> request(ResourceRequest::adopt(requestData));
889    MemoryCache::removeRequestFromSessionCaches(&context, *request);
890}
891
892void 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
909MemoryCache::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
951void 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
973void MemoryCache::evictResources()
974{
975    if (disabled())
976        return;
977
978    setDisabled(true);
979    setDisabled(false);
980}
981
982void 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
991void 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
999void 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
1020void 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
1048