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 "CachedCSSStyleSheet.h"
  27 #include "CachedFont.h"
  28 #include "CachedImage.h"
  29 #include "CachedScript.h"
  30 #include "CachedXSLStyleSheet.h"
  31 #include "CachedResourceLoader.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 "ResourceHandle.h"
  39 #include "SecurityOrigin.h"
  40 #include <stdio.h>
  41 #include <wtf/CurrentTime.h>
  42 #include <wtf/text/CString.h>
  43
  44 using namespace std;
  45
  46 namespace WebCore {
  47
  48 static const int cDefaultCacheCapacity = 8192 * 1024;
  49 static const double cMinDelayBeforeLiveDecodedPrune = 1; // Seconds.
  50 static const float cTargetPrunePercentage = .95f; // Percentage of capacity toward which we prune, to avoid immediately pruning again.
  51 static const double cDefaultDecodedDataDeletionInterval = 0;
  52
  53 MemoryCache* cache()
  54 {
  55     static MemoryCache* staticCache = new MemoryCache;
  56     return staticCache;
  57 }
  58
  59 MemoryCache::MemoryCache()
  60     : m_disabled(false)
  61     , m_pruneEnabled(true)
  62     , m_inPruneDeadResources(false)
  63     , m_capacity(cDefaultCacheCapacity)
  64     , m_minDeadCapacity(0)
  65     , m_maxDeadCapacity(cDefaultCacheCapacity)
  66     , m_deadDecodedDataDeletionInterval(cDefaultDecodedDataDeletionInterval)
  67     , m_liveSize(0)
  68     , m_deadSize(0)
  69 {
  70 }
  71
  72 static CachedResource* createResource(CachedResource::Type type, const KURL& url, const String& charset)
  73 {
  74     switch (type) {
  75     case CachedResource::ImageResource:
  76         return new CachedImage(url.string());
  77     case CachedResource::CSSStyleSheet:
  78         return new CachedCSSStyleSheet(url.string(), charset);
  79     case CachedResource::Script:
  80         return new CachedScript(url.string(), charset);
  81     case CachedResource::FontResource:
  82         return new CachedFont(url.string());
  83 #if ENABLE(XSLT)
  84     case CachedResource::XSLStyleSheet:
  85         return new CachedXSLStyleSheet(url.string());
  86 #endif
  87 #if ENABLE(LINK_PREFETCH)
  88     case CachedResource::LinkPrefetch:
  89         return new CachedResource(url.string(), CachedResource::LinkPrefetch);
  90 #endif
  91     default:
  92         break;
  93     }
  94
  95     return 0;
  96 }
  97
  98 CachedResource* MemoryCache::requestResource(CachedResourceLoader* cachedResourceLoader, CachedResource::Type type, const KURL& url, const String& charset, bool requestIsPreload)
  99 {
 100     LOG(ResourceLoading, "MemoryCache::requestResource '%s', charset '%s', preload=%u", url.string().latin1().data(), charset.latin1().data(), requestIsPreload);
 101
 102     // FIXME: Do we really need to special-case an empty URL?
 103     // Would it be better to just go on with the cache code and let it fail later?
 104     if (url.isEmpty())
 105         return 0;
 106
 107     // Look up the resource in our map.
 108     CachedResource* resource = resourceForURL(url.string());
 109
 110     if (resource && requestIsPreload && !resource->isPreloaded()) {
 111         LOG(ResourceLoading, "MemoryCache::requestResource already has a preload request for this request, and it hasn't been preloaded yet");
 112         return 0;
 113     }
 114
 115     if (!cachedResourceLoader->document()->securityOrigin()->canDisplay(url)) {
 116         LOG(ResourceLoading, "...URL was not allowed by SecurityOrigin");
 117         if (!requestIsPreload)
 118             FrameLoader::reportLocalLoadFailed(cachedResourceLoader->document()->frame(), url.string());
 119         return 0;
 120     }
 121
 122     if (!resource) {
 123         LOG(ResourceLoading, "CachedResource for '%s' wasn't found in cache. Creating it", url.string().latin1().data());
 124         // The resource does not exist. Create it.
 125         resource = createResource(type, url, charset);
 126         ASSERT(resource);
 127
 128         // Pretend the resource is in the cache, to prevent it from being deleted during the load() call.
 129         // FIXME: CachedResource should just use normal refcounting instead.
 130         resource->setInCache(true);
 131
 132         resource->load(cachedResourceLoader);
 133
 134         if (resource->errorOccurred()) {
 135             // We don't support immediate loads, but we do support immediate failure.
 136             // In that case we should to delete the resource now and return 0 because otherwise
 137             // it would leak if no ref/deref was ever done on it.
 138             resource->setInCache(false);
 139             delete resource;
 140             return 0;
 141         }
 142
 143         if (!disabled())
 144             m_resources.set(url.string(), resource);  // The size will be added in later once the resource is loaded and calls back to us with the new size.
 145         else {
 146             // Kick the resource out of the cache, because the cache is disabled.
 147             resource->setInCache(false);
 148             resource->setCachedResourceLoader(cachedResourceLoader);
 149         }
 150     }
 151
 152     if (resource->type() != type) {
 153         LOG(ResourceLoading, "MemoryCache::requestResource cannot use cached resource for '%s' due to type mismatch", url.string().latin1().data());
 154         return 0;
 155     }
 156
 157     if (!disabled()) {
 158         // This will move the resource to the front of its LRU list and increase its access count.
 159         resourceAccessed(resource);
 160     }
 161
 162     LOG(ResourceLoading, "MemoryCache::requestResource for '%s' returning resource %p\n", url.string().latin1().data(), resource);
 163
 164     return resource;
 165 }
 166
 167 CachedCSSStyleSheet* MemoryCache::requestUserCSSStyleSheet(CachedResourceLoader* cachedResourceLoader, const String& url, const String& charset)
 168 {
 169     CachedCSSStyleSheet* userSheet;
 170     if (CachedResource* existing = resourceForURL(url)) {
 171         if (existing->type() != CachedResource::CSSStyleSheet)
 172             return 0;
 173         userSheet = static_cast<CachedCSSStyleSheet*>(existing);
 174     } else {
 175         userSheet = new CachedCSSStyleSheet(url, charset);
 176
 177         // Pretend the resource is in the cache, to prevent it from being deleted during the load() call.
 178         // FIXME: CachedResource should just use normal refcounting instead.
 179         userSheet->setInCache(true);
 180         // Don't load incrementally, skip load checks, don't send resource load callbacks.
 181         userSheet->load(cachedResourceLoader, false, SkipSecurityCheck, false);
 182         if (!disabled())
 183             m_resources.set(url, userSheet);
 184         else
 185             userSheet->setInCache(false);
 186     }
 187
 188     if (!disabled()) {
 189         // This will move the resource to the front of its LRU list and increase its access count.
 190         resourceAccessed(userSheet);
 191     }
 192
 193     return userSheet;
 194 }
 195
 196 void MemoryCache::revalidateResource(CachedResource* resource, CachedResourceLoader* cachedResourceLoader)
 197 {
 198     ASSERT(resource);
 199     ASSERT(resource->inCache());
 200     ASSERT(resource == m_resources.get(resource->url()));
 201     ASSERT(!disabled());
 202     if (resource->resourceToRevalidate())
 203         return;
 204     if (!resource->canUseCacheValidator()) {
 205         evict(resource);
 206         return;
 207     }
 208     const String& url = resource->url();
 209     CachedResource* newResource = createResource(resource->type(), KURL(ParsedURLString, url), resource->encoding());
 210     LOG(ResourceLoading, "Resource %p created to revalidate %p", newResource, resource);
 211     newResource->setResourceToRevalidate(resource);
 212     evict(resource);
 213     m_resources.set(url, newResource);
 214     newResource->setInCache(true);
 215     resourceAccessed(newResource);
 216     newResource->load(cachedResourceLoader);
 217 }
 218
 219 void MemoryCache::revalidationSucceeded(CachedResource* revalidatingResource, const ResourceResponse& response)
 220 {
 221     CachedResource* resource = revalidatingResource->resourceToRevalidate();
 222     ASSERT(resource);
 223     ASSERT(!resource->inCache());
 224     ASSERT(resource->isLoaded());
 225     ASSERT(revalidatingResource->inCache());
 226
 227     evict(revalidatingResource);
 228
 229     ASSERT(!m_resources.get(resource->url()));
 230     m_resources.set(resource->url(), resource);
 231     resource->setInCache(true);
 232     resource->updateResponseAfterRevalidation(response);
 233     insertInLRUList(resource);
 234     int delta = resource->size();
 235     if (resource->decodedSize() && resource->hasClients())
 236         insertInLiveDecodedResourcesList(resource);
 237     if (delta)
 238         adjustSize(resource->hasClients(), delta);
 239
 240     revalidatingResource->switchClientsToRevalidatedResource();
 241     // this deletes the revalidating resource
 242     revalidatingResource->clearResourceToRevalidate();
 243 }
 244
 245 void MemoryCache::revalidationFailed(CachedResource* revalidatingResource)
 246 {
 247     LOG(ResourceLoading, "Revalidation failed for %p", revalidatingResource);
 248     ASSERT(revalidatingResource->resourceToRevalidate());
 249     revalidatingResource->clearResourceToRevalidate();
 250 }
 251
 252 CachedResource* MemoryCache::resourceForURL(const String& url)
 253 {
 254     CachedResource* resource = m_resources.get(url);
 255     bool wasPurgeable = MemoryCache::shouldMakeResourcePurgeableOnEviction() && resource && resource->isPurgeable();
 256     if (resource && !resource->makePurgeable(false)) {
 257         ASSERT(!resource->hasClients());
 258         evict(resource);
 259         return 0;
 260     }
 261     // Add the size back since we had subtracted it when we marked the memory as purgeable.
 262     if (wasPurgeable)
 263         adjustSize(resource->hasClients(), resource->size());
 264     return resource;
 265 }
 266
 267 unsigned MemoryCache::deadCapacity() const
 268 {
 269     // Dead resource capacity is whatever space is not occupied by live resources, bounded by an independent minimum and maximum.
 270     unsigned capacity = m_capacity - min(m_liveSize, m_capacity); // Start with available capacity.
 271     capacity = max(capacity, m_minDeadCapacity); // Make sure it's above the minimum.
 272     capacity = min(capacity, m_maxDeadCapacity); // Make sure it's below the maximum.
 273     return capacity;
 274 }
 275
 276 unsigned MemoryCache::liveCapacity() const
 277 {
 278     // Live resource capacity is whatever is left over after calculating dead resource capacity.
 279     return m_capacity - deadCapacity();
 280 }
 281
 282 void MemoryCache::pruneLiveResources()
 283 {
 284     if (!m_pruneEnabled)
 285         return;
 286
 287     unsigned capacity = liveCapacity();
 288     if (capacity && m_liveSize <= capacity)
 289         return;
 290
 291     unsigned targetSize = static_cast<unsigned>(capacity * cTargetPrunePercentage); // Cut by a percentage to avoid immediately pruning again.
 292     double currentTime = FrameView::currentPaintTimeStamp();
 293     if (!currentTime) // In case prune is called directly, outside of a Frame paint.
 294         currentTime = WTF::currentTime();
 295
 296     // Destroy any decoded data in live objects that we can.
 297     // Start from the tail, since this is the least recently accessed of the objects.
 298
 299     // The list might not be sorted by the m_lastDecodedAccessTime. The impact
 300     // of this weaker invariant is minor as the below if statement to check the
 301     // elapsedTime will evaluate to false as the currentTime will be a lot
 302     // greater than the current->m_lastDecodedAccessTime.
 303     // For more details see: https://bugs.webkit.org/show_bug.cgi?id=30209
 304     CachedResource* current = m_liveDecodedResources.m_tail;
 305     while (current) {
 306         CachedResource* prev = current->m_prevInLiveResourcesList;
 307         ASSERT(current->hasClients());
 308         if (current->isLoaded() && current->decodedSize()) {
 309             // Check to see if the remaining resources are too new to prune.
 310             double elapsedTime = currentTime - current->m_lastDecodedAccessTime;
 311             if (elapsedTime < cMinDelayBeforeLiveDecodedPrune)
 312                 return;
 313
 314             // Destroy our decoded data. This will remove us from
 315             // m_liveDecodedResources, and possibly move us to a different LRU
 316             // list in m_allResources.
 317             current->destroyDecodedData();
 318
 319             if (targetSize && m_liveSize <= targetSize)
 320                 return;
 321         }
 322         current = prev;
 323     }
 324 }
 325
 326 void MemoryCache::pruneDeadResources()
 327 {
 328     if (!m_pruneEnabled)
 329         return;
 330
 331     unsigned capacity = deadCapacity();
 332     if (capacity && m_deadSize <= capacity)
 333         return;
 334
 335     unsigned targetSize = static_cast<unsigned>(capacity * cTargetPrunePercentage); // Cut by a percentage to avoid immediately pruning again.
 336     int size = m_allResources.size();
 337
 338     if (!m_inPruneDeadResources) {
 339         // See if we have any purged resources we can evict.
 340         for (int i = 0; i < size; i++) {
 341             CachedResource* current = m_allResources[i].m_tail;
 342             while (current) {
 343                 CachedResource* prev = current->m_prevInAllResourcesList;
 344                 if (current->wasPurged()) {
 345                     ASSERT(!current->hasClients());
 346                     ASSERT(!current->isPreloaded());
 347                     evict(current);
 348                 }
 349                 current = prev;
 350             }
 351         }
 352         if (targetSize && m_deadSize <= targetSize)
 353             return;
 354     }
 355
 356     bool canShrinkLRULists = true;
 357     m_inPruneDeadResources = true;
 358     for (int i = size - 1; i >= 0; i--) {
 359         // Remove from the tail, since this is the least frequently accessed of the objects.
 360         CachedResource* current = m_allResources[i].m_tail;
 361
 362         // First flush all the decoded data in this queue.
 363         while (current) {
 364             CachedResource* prev = current->m_prevInAllResourcesList;
 365             if (!current->hasClients() && !current->isPreloaded() && current->isLoaded()) {
 366                 // Destroy our decoded data. This will remove us from
 367                 // m_liveDecodedResources, and possibly move us to a different
 368                 // LRU list in m_allResources.
 369                 current->destroyDecodedData();
 370
 371                 if (targetSize && m_deadSize <= targetSize) {
 372                     m_inPruneDeadResources = false;
 373                     return;
 374                 }
 375             }
 376             current = prev;
 377         }
 378
 379         // Now evict objects from this queue.
 380         current = m_allResources[i].m_tail;
 381         while (current) {
 382             CachedResource* prev = current->m_prevInAllResourcesList;
 383             if (!current->hasClients() && !current->isPreloaded() && !current->isCacheValidator()) {
 384                 if (!makeResourcePurgeable(current))
 385                     evict(current);
 386
 387                 // If evict() caused pruneDeadResources() to be re-entered, bail out. This can happen when removing an
 388                 // SVG CachedImage that has subresources.
 389                 if (!m_inPruneDeadResources)
 390                     return;
 391
 392                 if (targetSize && m_deadSize <= targetSize) {
 393                     m_inPruneDeadResources = false;
 394                     return;
 395                 }
 396             }
 397             current = prev;
 398         }
 399
 400         // Shrink the vector back down so we don't waste time inspecting
 401         // empty LRU lists on future prunes.
 402         if (m_allResources[i].m_head)
 403             canShrinkLRULists = false;
 404         else if (canShrinkLRULists)
 405             m_allResources.resize(i);
 406     }
 407     m_inPruneDeadResources = false;
 408 }
 409
 410 void MemoryCache::setCapacities(unsigned minDeadBytes, unsigned maxDeadBytes, unsigned totalBytes)
 411 {
 412     ASSERT(minDeadBytes <= maxDeadBytes);
 413     ASSERT(maxDeadBytes <= totalBytes);
 414     m_minDeadCapacity = minDeadBytes;
 415     m_maxDeadCapacity = maxDeadBytes;
 416     m_capacity = totalBytes;
 417     prune();
 418 }
 419
 420 bool MemoryCache::makeResourcePurgeable(CachedResource* resource)
 421 {
 422     if (!MemoryCache::shouldMakeResourcePurgeableOnEviction())
 423         return false;
 424
 425     if (!resource->inCache())
 426         return false;
 427
 428     if (resource->isPurgeable())
 429         return true;
 430
 431     if (!resource->isSafeToMakePurgeable())
 432         return false;
 433
 434     if (!resource->makePurgeable(true))
 435         return false;
 436
 437     adjustSize(resource->hasClients(), -static_cast<int>(resource->size()));
 438
 439     return true;
 440 }
 441
 442 void MemoryCache::evict(CachedResource* resource)
 443 {
 444     LOG(ResourceLoading, "Evicting resource %p for '%s' from cache", resource, resource->url().latin1().data());
 445     // The resource may have already been removed by someone other than our caller,
 446     // who needed a fresh copy for a reload. See <http://bugs.webkit.org/show_bug.cgi?id=12479#c6>.
 447     if (resource->inCache()) {
 448         // Remove from the resource map.
 449         m_resources.remove(resource->url());
 450         resource->setInCache(false);
 451
 452         // Remove from the appropriate LRU list.
 453         removeFromLRUList(resource);
 454         removeFromLiveDecodedResourcesList(resource);
 455
 456         // If the resource was purged, it means we had already decremented the size when we made the
 457         // resource purgeable in makeResourcePurgeable(). So adjust the size if we are evicting a
 458         // resource that was not marked as purgeable.
 459         if (!MemoryCache::shouldMakeResourcePurgeableOnEviction() || !resource->isPurgeable())
 460             adjustSize(resource->hasClients(), -static_cast<int>(resource->size()));
 461     } else
 462         ASSERT(m_resources.get(resource->url()) != resource);
 463
 464     if (resource->canDelete())
 465         delete resource;
 466 }
 467
 468 void MemoryCache::addCachedResourceLoader(CachedResourceLoader* cachedResourceLoader)
 469 {
 470     m_cachedResourceLoaders.add(cachedResourceLoader);
 471 }
 472
 473 void MemoryCache::removeCachedResourceLoader(CachedResourceLoader* cachedResourceLoader)
 474 {
 475     m_cachedResourceLoaders.remove(cachedResourceLoader);
 476 }
 477
 478 static inline unsigned fastLog2(unsigned i)
 479 {
 480     unsigned log2 = 0;
 481     if (i & (i - 1))
 482         log2 += 1;
 483     if (i >> 16)
 484         log2 += 16, i >>= 16;
 485     if (i >> 8)
 486         log2 += 8, i >>= 8;
 487     if (i >> 4)
 488         log2 += 4, i >>= 4;
 489     if (i >> 2)
 490         log2 += 2, i >>= 2;
 491     if (i >> 1)
 492         log2 += 1;
 493     return log2;
 494 }
 495
 496 MemoryCache::LRUList* MemoryCache::lruListFor(CachedResource* resource)
 497 {
 498     unsigned accessCount = max(resource->accessCount(), 1U);
 499     unsigned queueIndex = fastLog2(resource->size() / accessCount);
 500 #ifndef NDEBUG
 501     resource->m_lruIndex = queueIndex;
 502 #endif
 503     if (m_allResources.size() <= queueIndex)
 504         m_allResources.grow(queueIndex + 1);
 505     return &m_allResources[queueIndex];
 506 }
 507
 508 void MemoryCache::removeFromLRUList(CachedResource* resource)
 509 {
 510     // If we've never been accessed, then we're brand new and not in any list.
 511     if (resource->accessCount() == 0)
 512         return;
 513
 514 #if !ASSERT_DISABLED
 515     unsigned oldListIndex = resource->m_lruIndex;
 516 #endif
 517
 518     LRUList* list = lruListFor(resource);
 519
 520 #if !ASSERT_DISABLED
 521     // Verify that the list we got is the list we want.
 522     ASSERT(resource->m_lruIndex == oldListIndex);
 523
 524     // Verify that we are in fact in this list.
 525     bool found = false;
 526     for (CachedResource* current = list->m_head; current; current = current->m_nextInAllResourcesList) {
 527         if (current == resource) {
 528             found = true;
 529             break;
 530         }
 531     }
 532     ASSERT(found);
 533 #endif
 534
 535     CachedResource* next = resource->m_nextInAllResourcesList;
 536     CachedResource* prev = resource->m_prevInAllResourcesList;
 537
 538     if (next == 0 && prev == 0 && list->m_head != resource)
 539         return;
 540
 541     resource->m_nextInAllResourcesList = 0;
 542     resource->m_prevInAllResourcesList = 0;
 543
 544     if (next)
 545         next->m_prevInAllResourcesList = prev;
 546     else if (list->m_tail == resource)
 547         list->m_tail = prev;
 548
 549     if (prev)
 550         prev->m_nextInAllResourcesList = next;
 551     else if (list->m_head == resource)
 552         list->m_head = next;
 553 }
 554
 555 void MemoryCache::insertInLRUList(CachedResource* resource)
 556 {
 557     // Make sure we aren't in some list already.
 558     ASSERT(!resource->m_nextInAllResourcesList && !resource->m_prevInAllResourcesList);
 559     ASSERT(resource->inCache());
 560     ASSERT(resource->accessCount() > 0);
 561
 562     LRUList* list = lruListFor(resource);
 563
 564     resource->m_nextInAllResourcesList = list->m_head;
 565     if (list->m_head)
 566         list->m_head->m_prevInAllResourcesList = resource;
 567     list->m_head = resource;
 568
 569     if (!resource->m_nextInAllResourcesList)
 570         list->m_tail = resource;
 571
 572 #ifndef NDEBUG
 573     // Verify that we are in now in the list like we should be.
 574     list = lruListFor(resource);
 575     bool found = false;
 576     for (CachedResource* current = list->m_head; current; current = current->m_nextInAllResourcesList) {
 577         if (current == resource) {
 578             found = true;
 579             break;
 580         }
 581     }
 582     ASSERT(found);
 583 #endif
 584
 585 }
 586
 587 void MemoryCache::resourceAccessed(CachedResource* resource)
 588 {
 589     ASSERT(resource->inCache());
 590
 591     // Need to make sure to remove before we increase the access count, since
 592     // the queue will possibly change.
 593     removeFromLRUList(resource);
 594
 595     // If this is the first time the resource has been accessed, adjust the size of the cache to account for its initial size.
 596     if (!resource->accessCount())
 597         adjustSize(resource->hasClients(), resource->size());
 598
 599     // Add to our access count.
 600     resource->increaseAccessCount();
 601
 602     // Now insert into the new queue.
 603     insertInLRUList(resource);
 604 }
 605
 606 void MemoryCache::removeFromLiveDecodedResourcesList(CachedResource* resource)
 607 {
 608     // If we've never been accessed, then we're brand new and not in any list.
 609     if (!resource->m_inLiveDecodedResourcesList)
 610         return;
 611     resource->m_inLiveDecodedResourcesList = false;
 612
 613 #ifndef NDEBUG
 614     // Verify that we are in fact in this list.
 615     bool found = false;
 616     for (CachedResource* current = m_liveDecodedResources.m_head; current; current = current->m_nextInLiveResourcesList) {
 617         if (current == resource) {
 618             found = true;
 619             break;
 620         }
 621     }
 622     ASSERT(found);
 623 #endif
 624
 625     CachedResource* next = resource->m_nextInLiveResourcesList;
 626     CachedResource* prev = resource->m_prevInLiveResourcesList;
 627
 628     if (next == 0 && prev == 0 && m_liveDecodedResources.m_head != resource)
 629         return;
 630
 631     resource->m_nextInLiveResourcesList = 0;
 632     resource->m_prevInLiveResourcesList = 0;
 633
 634     if (next)
 635         next->m_prevInLiveResourcesList = prev;
 636     else if (m_liveDecodedResources.m_tail == resource)
 637         m_liveDecodedResources.m_tail = prev;
 638
 639     if (prev)
 640         prev->m_nextInLiveResourcesList = next;
 641     else if (m_liveDecodedResources.m_head == resource)
 642         m_liveDecodedResources.m_head = next;
 643 }
 644
 645 void MemoryCache::insertInLiveDecodedResourcesList(CachedResource* resource)
 646 {
 647     // Make sure we aren't in the list already.
 648     ASSERT(!resource->m_nextInLiveResourcesList && !resource->m_prevInLiveResourcesList && !resource->m_inLiveDecodedResourcesList);
 649     resource->m_inLiveDecodedResourcesList = true;
 650
 651     resource->m_nextInLiveResourcesList = m_liveDecodedResources.m_head;
 652     if (m_liveDecodedResources.m_head)
 653         m_liveDecodedResources.m_head->m_prevInLiveResourcesList = resource;
 654     m_liveDecodedResources.m_head = resource;
 655
 656     if (!resource->m_nextInLiveResourcesList)
 657         m_liveDecodedResources.m_tail = resource;
 658
 659 #ifndef NDEBUG
 660     // Verify that we are in now in the list like we should be.
 661     bool found = false;
 662     for (CachedResource* current = m_liveDecodedResources.m_head; current; current = current->m_nextInLiveResourcesList) {
 663         if (current == resource) {
 664             found = true;
 665             break;
 666         }
 667     }
 668     ASSERT(found);
 669 #endif
 670
 671 }
 672
 673 void MemoryCache::addToLiveResourcesSize(CachedResource* resource)
 674 {
 675     m_liveSize += resource->size();
 676     m_deadSize -= resource->size();
 677 }
 678
 679 void MemoryCache::removeFromLiveResourcesSize(CachedResource* resource)
 680 {
 681     m_liveSize -= resource->size();
 682     m_deadSize += resource->size();
 683 }
 684
 685 void MemoryCache::adjustSize(bool live, int delta)
 686 {
 687     if (live) {
 688         ASSERT(delta >= 0 || ((int)m_liveSize + delta >= 0));
 689         m_liveSize += delta;
 690     } else {
 691         ASSERT(delta >= 0 || ((int)m_deadSize + delta >= 0));
 692         m_deadSize += delta;
 693     }
 694 }
 695
 696 void MemoryCache::TypeStatistic::addResource(CachedResource* o)
 697 {
 698     bool purged = o->wasPurged();
 699     bool purgeable = o->isPurgeable() && !purged;
 700     int pageSize = (o->encodedSize() + o->overheadSize() + 4095) & ~4095;
 701     count++;
 702     size += purged ? 0 : o->size();
 703     liveSize += o->hasClients() ? o->size() : 0;
 704     decodedSize += o->decodedSize();
 705     purgeableSize += purgeable ? pageSize : 0;
 706     purgedSize += purged ? pageSize : 0;
 707 }
 708
 709 MemoryCache::Statistics MemoryCache::getStatistics()
 710 {
 711     Statistics stats;
 712     CachedResourceMap::iterator e = m_resources.end();
 713     for (CachedResourceMap::iterator i = m_resources.begin(); i != e; ++i) {
 714         CachedResource* resource = i->second;
 715         switch (resource->type()) {
 716         case CachedResource::ImageResource:
 717             stats.images.addResource(resource);
 718             break;
 719         case CachedResource::CSSStyleSheet:
 720             stats.cssStyleSheets.addResource(resource);
 721             break;
 722         case CachedResource::Script:
 723             stats.scripts.addResource(resource);
 724             break;
 725 #if ENABLE(XSLT)
 726         case CachedResource::XSLStyleSheet:
 727             stats.xslStyleSheets.addResource(resource);
 728             break;
 729 #endif
 730         case CachedResource::FontResource:
 731             stats.fonts.addResource(resource);
 732             break;
 733         default:
 734             break;
 735         }
 736     }
 737     return stats;
 738 }
 739
 740 void MemoryCache::setDisabled(bool disabled)
 741 {
 742     m_disabled = disabled;
 743     if (!m_disabled)
 744         return;
 745
 746     for (;;) {
 747         CachedResourceMap::iterator i = m_resources.begin();
 748         if (i == m_resources.end())
 749             break;
 750         evict(i->second);
 751     }
 752 }
 753
 754 #ifndef NDEBUG
 755 void MemoryCache::dumpStats()
 756 {
 757     Statistics s = getStatistics();
 758     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s\n", "", "Count", "Size", "LiveSize", "DecodedSize", "PurgeableSize", "PurgedSize");
 759     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s\n", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------");
 760     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);
 761     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);
 762 #if ENABLE(XSLT)
 763     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);
 764 #endif
 765     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);
 766     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);
 767     printf("%-13s %-13s %-13s %-13s %-13s %-13s %-13s\n\n", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------", "-------------");
 768 }
 769
 770 void MemoryCache::dumpLRULists(bool includeLive) const
 771 {
 772     printf("LRU-SP lists in eviction order (Kilobytes decoded, Kilobytes encoded, Access count, Referenced, isPurgeable, wasPurged):\n");
 773
 774     int size = m_allResources.size();
 775     for (int i = size - 1; i >= 0; i--) {
 776         printf("\n\nList %d: ", i);
 777         CachedResource* current = m_allResources[i].m_tail;
 778         while (current) {
 779             CachedResource* prev = current->m_prevInAllResourcesList;
 780             if (includeLive || !current->hasClients())
 781                 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());
 782
 783             current = prev;
 784         }
 785     }
 786 }
 787 #endif
 788
 789 } // namespace WebCore