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