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