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