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