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