third_party/WebKit/Source/core/fetch/MemoryCache.h

   1 /*
   2     Copyright (C) 1998 Lars Knoll (knoll@mpi-hd.mpg.de)
   3     Copyright (C) 2001 Dirk Mueller <mueller@kde.org>
   4     Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   5
   6     This library is free software; you can redistribute it and/or
   7     modify it under the terms of the GNU Library General Public
   8     License as published by the Free Software Foundation; either
   9     version 2 of the License, or (at your option) any later version.
  10
  11     This library is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14     Library General Public License for more details.
  15
  16     You should have received a copy of the GNU Library General Public License
  17     along with this library; see the file COPYING.LIB.  If not, write to
  18     the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  19     Boston, MA 02110-1301, USA.
  20
  21     This class provides all functionality needed for loading images, style sheets and html
  22     pages from the web. It has a memory cache for these objects.
  23 */
  24
  25 #ifndef MemoryCache_h
  26 #define MemoryCache_h
  27
  28 #include "core/CoreExport.h"
  29 #include "core/fetch/Resource.h"
  30 #include "core/fetch/ResourcePtr.h"
  31 #include "public/platform/WebThread.h"
  32 #include "wtf/Allocator.h"
  33 #include "wtf/HashMap.h"
  34 #include "wtf/Noncopyable.h"
  35 #include "wtf/Vector.h"
  36 #include "wtf/text/StringHash.h"
  37 #include "wtf/text/WTFString.h"
  38
  39 namespace blink  {
  40
  41 class Resource;
  42 class KURL;
  43 class ExecutionContext;
  44
  45 // This cache holds subresources used by Web pages: images, scripts, stylesheets, etc.
  46
  47 // The cache keeps a flexible but bounded window of dead resources that grows/shrinks
  48 // depending on the live resource load. Here's an example of cache growth over time,
  49 // with a min dead resource capacity of 25% and a max dead resource capacity of 50%:
  50
  51 //        |-----|                              Dead: -
  52 //        |----------|                         Live: +
  53 //      --|----------|                         Cache boundary: | (objects outside this mark have been evicted)
  54 //      --|----------++++++++++|
  55 // -------|-----+++++++++++++++|
  56 // -------|-----+++++++++++++++|+++++
  57
  58 // Enable this macro to periodically log information about the memory cache.
  59 #undef MEMORY_CACHE_STATS
  60
  61 // Determines the order in which CachedResources are evicted
  62 // from the decoded resources cache.
  63 enum MemoryCacheLiveResourcePriority {
  64     MemoryCacheLiveResourcePriorityLow = 0,
  65     MemoryCacheLiveResourcePriorityHigh,
  66     MemoryCacheLiveResourcePriorityUnknown
  67 };
  68
  69 enum UpdateReason {
  70     UpdateForAccess,
  71     UpdateForPropertyChange
  72 };
  73
  74 // MemoryCacheEntry class is used only in MemoryCache class, but we don't make
  75 // MemoryCacheEntry class an inner class of MemoryCache because of dependency
  76 // from MemoryCacheLRUList.
  77 class MemoryCacheEntry final : public GarbageCollectedFinalized<MemoryCacheEntry> {
  78 public:
  79     static MemoryCacheEntry* create(Resource* resource)
  80     {
  81         return new MemoryCacheEntry(resource);
  82     }
  83     DECLARE_TRACE();
  84     void dispose();
  85
  86     ResourcePtr<Resource> m_resource;
  87     bool m_inLiveDecodedResourcesList;
  88     unsigned m_accessCount;
  89     MemoryCacheLiveResourcePriority m_liveResourcePriority;
  90     double m_lastDecodedAccessTime; // Used as a thrash guard
  91
  92     Member<MemoryCacheEntry> m_previousInLiveResourcesList;
  93     Member<MemoryCacheEntry> m_nextInLiveResourcesList;
  94     Member<MemoryCacheEntry> m_previousInAllResourcesList;
  95     Member<MemoryCacheEntry> m_nextInAllResourcesList;
  96
  97 private:
  98     explicit MemoryCacheEntry(Resource* resource)
  99         : m_resource(resource)
 100         , m_inLiveDecodedResourcesList(false)
 101         , m_accessCount(0)
 102         , m_liveResourcePriority(MemoryCacheLiveResourcePriorityLow)
 103         , m_lastDecodedAccessTime(0.0)
 104         , m_previousInLiveResourcesList(nullptr)
 105         , m_nextInLiveResourcesList(nullptr)
 106         , m_previousInAllResourcesList(nullptr)
 107         , m_nextInAllResourcesList(nullptr)
 108     {
 109     }
 110 };
 111
 112 WILL_NOT_BE_EAGERLY_TRACED_CLASS(MemoryCacheEntry);
 113
 114 // MemoryCacheLRUList is used only in MemoryCache class, but we don't make
 115 // MemoryCacheLRUList an inner struct of MemoryCache because we can't define
 116 // VectorTraits for inner structs.
 117 struct MemoryCacheLRUList final {
 118     ALLOW_ONLY_INLINE_ALLOCATION();
 119 public:
 120     Member<MemoryCacheEntry> m_head;
 121     Member<MemoryCacheEntry> m_tail;
 122
 123     MemoryCacheLRUList() : m_head(nullptr), m_tail(nullptr) { }
 124     DECLARE_TRACE();
 125 };
 126
 127 }
 128
 129 WTF_ALLOW_MOVE_INIT_AND_COMPARE_WITH_MEM_FUNCTIONS(blink::MemoryCacheLRUList);
 130
 131 namespace blink {
 132
 133 class CORE_EXPORT MemoryCache final : public GarbageCollectedFinalized<MemoryCache>, public WebThread::TaskObserver {
 134     WTF_MAKE_NONCOPYABLE(MemoryCache);
 135 public:
 136     static MemoryCache* create();
 137     ~MemoryCache();
 138     DECLARE_TRACE();
 139
 140     struct TypeStatistic {
 141         STACK_ALLOCATED();
 142         size_t count;
 143         size_t size;
 144         size_t liveSize;
 145         size_t decodedSize;
 146         size_t encodedSize;
 147         size_t encodedSizeDuplicatedInDataURLs;
 148         size_t purgeableSize;
 149         size_t purgedSize;
 150
 151         TypeStatistic()
 152             : count(0)
 153             , size(0)
 154             , liveSize(0)
 155             , decodedSize(0)
 156             , encodedSize(0)
 157             , encodedSizeDuplicatedInDataURLs(0)
 158             , purgeableSize(0)
 159             , purgedSize(0)
 160         {
 161         }
 162
 163         void addResource(Resource*);
 164     };
 165
 166     struct Statistics {
 167         STACK_ALLOCATED();
 168         TypeStatistic images;
 169         TypeStatistic cssStyleSheets;
 170         TypeStatistic scripts;
 171         TypeStatistic xslStyleSheets;
 172         TypeStatistic fonts;
 173         TypeStatistic other;
 174     };
 175
 176     Resource* resourceForURL(const KURL&);
 177     Resource* resourceForURL(const KURL&, const String& cacheIdentifier);
 178     WillBeHeapVector<RawPtrWillBeMember<Resource>> resourcesForURL(const KURL&);
 179
 180     void add(Resource*);
 181     void replace(Resource* newResource, Resource* oldResource);
 182     void remove(Resource*);
 183     bool contains(const Resource*) const;
 184
 185     static KURL removeFragmentIdentifierIfNeeded(const KURL& originalURL);
 186
 187     static String defaultCacheIdentifier();
 188
 189     // Sets the cache's memory capacities, in bytes. These will hold only approximately,
 190     // since the decoded cost of resources like scripts and stylesheets is not known.
 191     //  - minDeadBytes: The maximum number of bytes that dead resources should consume when the cache is under pressure.
 192     //  - maxDeadBytes: The maximum number of bytes that dead resources should consume when the cache is not under pressure.
 193     //  - totalBytes: The maximum number of bytes that the cache should consume overall.
 194     void setCapacities(size_t minDeadBytes, size_t maxDeadBytes, size_t totalBytes);
 195     void setDelayBeforeLiveDecodedPrune(double seconds) { m_delayBeforeLiveDecodedPrune = seconds; }
 196     void setMaxPruneDeferralDelay(double seconds) { m_maxPruneDeferralDelay = seconds; }
 197
 198     void evictResources();
 199
 200     void prune(Resource* justReleasedResource = 0);
 201
 202     // Called to adjust a resource's size, lru list position, and access count.
 203     void update(Resource*, size_t oldSize, size_t newSize, bool wasAccessed = false);
 204     void updateForAccess(Resource* resource) { update(resource, resource->size(), resource->size(), true); }
 205     void updateDecodedResource(Resource*, UpdateReason, MemoryCacheLiveResourcePriority = MemoryCacheLiveResourcePriorityUnknown);
 206
 207     void makeLive(Resource*);
 208     void makeDead(Resource*);
 209
 210     // This should be called when a Resource object is created.
 211     void registerLiveResource(Resource&);
 212     // This should be called when a Resource object becomes unnecesarry.
 213     void unregisterLiveResource(Resource&);
 214
 215     void removeURLFromCache(const KURL&);
 216
 217     Statistics getStatistics();
 218
 219     size_t minDeadCapacity() const { return m_minDeadCapacity; }
 220     size_t maxDeadCapacity() const { return m_maxDeadCapacity; }
 221     size_t capacity() const { return m_capacity; }
 222     size_t liveSize() const { return m_liveSize; }
 223     size_t deadSize() const { return m_deadSize; }
 224
 225     // Exposed for testing
 226     MemoryCacheLiveResourcePriority priority(Resource*) const;
 227
 228     // TaskObserver implementation
 229     void willProcessTask() override;
 230     void didProcessTask() override;
 231
 232     void pruneAll();
 233
 234     void updateFramePaintTimestamp();
 235
 236 private:
 237     enum PruneStrategy {
 238         // Automatically decide how much to prune.
 239         AutomaticPrune,
 240         // Maximally prune resources.
 241         MaximalPrune
 242     };
 243
 244     MemoryCache();
 245
 246     MemoryCacheLRUList* lruListFor(unsigned accessCount, size_t);
 247
 248 #ifdef MEMORY_CACHE_STATS
 249     void dumpStats(Timer<MemoryCache>*);
 250     void dumpLRULists(bool includeLive) const;
 251 #endif
 252
 253     // Calls to put the cached resource into and out of LRU lists.
 254     void insertInLRUList(MemoryCacheEntry*, MemoryCacheLRUList*);
 255     void removeFromLRUList(MemoryCacheEntry*, MemoryCacheLRUList*);
 256     bool containedInLRUList(MemoryCacheEntry*, MemoryCacheLRUList*);
 257
 258     // Track decoded resources that are in the cache and referenced by a Web page.
 259     void insertInLiveDecodedResourcesList(MemoryCacheEntry*);
 260     void removeFromLiveDecodedResourcesList(MemoryCacheEntry*);
 261     bool containedInLiveDecodedResourcesList(MemoryCacheEntry*);
 262
 263     size_t liveCapacity() const;
 264     size_t deadCapacity() const;
 265
 266     // pruneDeadResources() - Flush decoded and encoded data from resources not referenced by Web pages.
 267     // pruneLiveResources() - Flush decoded data from resources still referenced by Web pages.
 268     void pruneDeadResources(PruneStrategy);
 269     void pruneLiveResources(PruneStrategy);
 270     void pruneNow(double currentTime, PruneStrategy);
 271
 272     bool evict(MemoryCacheEntry*);
 273
 274     MemoryCacheEntry* getEntryForResource(const Resource*) const;
 275
 276     static void removeURLFromCacheInternal(ExecutionContext*, const KURL&);
 277
 278     bool m_inPruneResources;
 279     bool m_prunePending;
 280     double m_maxPruneDeferralDelay;
 281     double m_pruneTimeStamp;
 282     double m_pruneFrameTimeStamp;
 283     double m_lastFramePaintTimeStamp; // used for detecting decoded resource thrash in the cache
 284
 285     size_t m_capacity;
 286     size_t m_minDeadCapacity;
 287     size_t m_maxDeadCapacity;
 288     size_t m_maxDeferredPruneDeadCapacity;
 289     double m_delayBeforeLiveDecodedPrune;
 290
 291     size_t m_liveSize; // The number of bytes currently consumed by "live" resources in the cache.
 292     size_t m_deadSize; // The number of bytes currently consumed by "dead" resources in the cache.
 293
 294     // Size-adjusted and popularity-aware LRU list collection for cache objects. This collection can hold
 295     // more resources than the cached resource map, since it can also hold "stale" multiple versions of objects that are
 296     // waiting to die when the clients referencing them go away.
 297     HeapVector<MemoryCacheLRUList, 32> m_allResources;
 298
 299     // Lists just for live resources with decoded data. Access to this list is based off of painting the resource.
 300     // The lists are ordered by decode priority, with higher indices having higher priorities.
 301     MemoryCacheLRUList m_liveDecodedResources[MemoryCacheLiveResourcePriorityHigh + 1];
 302
 303     // A URL-based map of all resources that are in the cache (including the freshest version of objects that are currently being
 304     // referenced by a Web page).
 305     using ResourceMap = HeapHashMap<String, Member<MemoryCacheEntry>>;
 306     using ResourceMapIndex = HeapHashMap<String, Member<ResourceMap>>;
 307     ResourceMap* ensureResourceMap(const String& cacheIdentifier);
 308     ResourceMapIndex m_resourceMaps;
 309
 310 #if ENABLE(OILPAN)
 311     // Unlike m_allResources, m_liveResources is a set of Resource objects which
 312     // should not be deleted. m_allResources only contains on-cache Resource
 313     // objects.
 314     // FIXME: Can we remove manual lifetime management of Resource and this?
 315     HeapHashSet<Member<Resource>> m_liveResources;
 316     friend CORE_EXPORT MemoryCache* replaceMemoryCacheForTesting(MemoryCache*);
 317 #endif
 318
 319     friend class MemoryCacheTest;
 320 #ifdef MEMORY_CACHE_STATS
 321     Timer<MemoryCache> m_statsTimer;
 322 #endif
 323 };
 324
 325 // Returns the global cache.
 326 CORE_EXPORT MemoryCache* memoryCache();
 327
 328 // Sets the global cache, used to swap in a test instance. Returns the old
 329 // MemoryCache object.
 330 CORE_EXPORT MemoryCache* replaceMemoryCacheForTesting(MemoryCache*);
 331
 332 }
 333
 334 #endif