Replace use of WTF::FixedArray with std::array
[WebKit-https.git] / Source / JavaScriptCore / runtime / CodeCache.h
1 /*
2  * Copyright (C) 2012, 2013 Apple Inc. All Rights Reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #ifndef CodeCache_h
27 #define CodeCache_h
28
29 #include "CodeSpecializationKind.h"
30 #include "ParserModes.h"
31 #include "SourceCode.h"
32 #include "Strong.h"
33 #include "WeakRandom.h"
34 #include <wtf/CurrentTime.h>
35 #include <wtf/Forward.h>
36 #include <wtf/PassOwnPtr.h>
37 #include <wtf/RandomNumber.h>
38 #include <wtf/text/WTFString.h>
39
40 namespace JSC {
41
42 class EvalExecutable;
43 class FunctionBodyNode;
44 class Identifier;
45 class JSScope;
46 class ProgramExecutable;
47 class UnlinkedCodeBlock;
48 class UnlinkedEvalCodeBlock;
49 class UnlinkedFunctionCodeBlock;
50 class UnlinkedFunctionExecutable;
51 class UnlinkedProgramCodeBlock;
52 class VM;
53 struct ParserError;
54 class SourceCode;
55 class SourceProvider;
56
57 class SourceCodeKey {
58 public:
59     enum CodeType { EvalType, ProgramType, FunctionType };
60
61     SourceCodeKey()
62     {
63     }
64
65     SourceCodeKey(const SourceCode& sourceCode, const String& name, CodeType codeType, JSParserStrictness jsParserStrictness)
66         : m_sourceCode(sourceCode)
67         , m_name(name)
68         , m_flags((codeType << 1) | jsParserStrictness)
69         , m_hash(string().impl()->hash())
70     {
71     }
72
73     SourceCodeKey(WTF::HashTableDeletedValueType)
74         : m_sourceCode(WTF::HashTableDeletedValue)
75     {
76     }
77
78     bool isHashTableDeletedValue() const { return m_sourceCode.isHashTableDeletedValue(); }
79
80     unsigned hash() const { return m_hash; }
81
82     size_t length() const { return m_sourceCode.length(); }
83
84     bool isNull() const { return m_sourceCode.isNull(); }
85
86     // To save memory, we compute our string on demand. It's expected that source
87     // providers cache their strings to make this efficient.
88     String string() const { return m_sourceCode.toString(); }
89
90     bool operator==(const SourceCodeKey& other) const
91     {
92         return m_hash == other.m_hash
93             && length() == other.length()
94             && m_flags == other.m_flags
95             && m_name == other.m_name
96             && string() == other.string();
97     }
98
99 private:
100     SourceCode m_sourceCode;
101     String m_name;
102     unsigned m_flags;
103     unsigned m_hash;
104 };
105
106 struct SourceCodeKeyHash {
107     static unsigned hash(const SourceCodeKey& key) { return key.hash(); }
108     static bool equal(const SourceCodeKey& a, const SourceCodeKey& b) { return a == b; }
109     static const bool safeToCompareToEmptyOrDeleted = false;
110 };
111
112 struct SourceCodeKeyHashTraits : SimpleClassHashTraits<SourceCodeKey> {
113     static const bool hasIsEmptyValueFunction = true;
114     static bool isEmptyValue(const SourceCodeKey& sourceCodeKey) { return sourceCodeKey.isNull(); }
115 };
116
117 struct SourceCodeValue {
118     SourceCodeValue()
119     {
120     }
121
122     SourceCodeValue(VM& vm, JSCell* cell, int64_t age)
123         : cell(vm, cell)
124         , age(age)
125     {
126     }
127
128     Strong<JSCell> cell;
129     int64_t age;
130 };
131
132 class CodeCacheMap {
133 public:
134     typedef HashMap<SourceCodeKey, SourceCodeValue, SourceCodeKeyHash, SourceCodeKeyHashTraits> MapType;
135     typedef MapType::iterator iterator;
136     typedef MapType::AddResult AddResult;
137
138     CodeCacheMap()
139         : m_size(0)
140         , m_sizeAtLastPrune(0)
141         , m_timeAtLastPrune(monotonicallyIncreasingTime())
142         , m_minCapacity(0)
143         , m_capacity(0)
144         , m_age(0)
145     {
146     }
147
148     AddResult add(const SourceCodeKey& key, const SourceCodeValue& value)
149     {
150         prune();
151
152         AddResult addResult = m_map.add(key, value);
153         if (addResult.isNewEntry) {
154             m_size += key.length();
155             m_age += key.length();
156             return addResult;
157         }
158
159         int64_t age = m_age - addResult.iterator->value.age;
160         if (age > m_capacity) {
161             // A requested object is older than the cache's capacity. We can
162             // infer that requested objects are subject to high eviction probability,
163             // so we grow the cache to improve our hit rate.
164             m_capacity += recencyBias * oldObjectSamplingMultiplier * key.length();
165         } else if (age < m_capacity / 2) {
166             // A requested object is much younger than the cache's capacity. We can
167             // infer that requested objects are subject to low eviction probability,
168             // so we shrink the cache to save memory.
169             m_capacity -= recencyBias * key.length();
170             if (m_capacity < m_minCapacity)
171                 m_capacity = m_minCapacity;
172         }
173
174         addResult.iterator->value.age = m_age;
175         m_age += key.length();
176         return addResult;
177     }
178
179     void remove(iterator it)
180     {
181         m_size -= it->key.length();
182         m_map.remove(it);
183     }
184
185     void clear()
186     {
187         m_size = 0;
188         m_age = 0;
189         m_map.clear();
190     }
191
192     int64_t age() { return m_age; }
193
194 private:
195     // This constant factor biases cache capacity toward allowing a minimum
196     // working set to enter the cache before it starts evicting.
197     static const double workingSetTime;
198     static const int64_t workingSetMaxBytes = 16000000;
199     static const size_t workingSetMaxEntries = 2000;
200
201     // This constant factor biases cache capacity toward recent activity. We
202     // want to adapt to changing workloads.
203     static const int64_t recencyBias = 4;
204
205     // This constant factor treats a sampled event for one old object as if it
206     // happened for many old objects. Most old objects are evicted before we can
207     // sample them, so we need to extrapolate from the ones we do sample.
208     static const int64_t oldObjectSamplingMultiplier = 32;
209
210     size_t numberOfEntries() const { return static_cast<size_t>(m_map.size()); }
211     bool canPruneQuickly() const { return numberOfEntries() < workingSetMaxEntries; }
212
213     void pruneSlowCase();
214     void prune()
215     {
216         if (m_size <= m_capacity && canPruneQuickly())
217             return;
218
219         if (monotonicallyIncreasingTime() - m_timeAtLastPrune < workingSetTime
220             && m_size - m_sizeAtLastPrune < workingSetMaxBytes
221             && canPruneQuickly())
222                 return;
223
224         pruneSlowCase();
225     }
226
227     MapType m_map;
228     int64_t m_size;
229     int64_t m_sizeAtLastPrune;
230     double m_timeAtLastPrune;
231     int64_t m_minCapacity;
232     int64_t m_capacity;
233     int64_t m_age;
234 };
235
236 // Caches top-level code such as <script>, eval(), new Function, and JSEvaluateScript().
237 class CodeCache {
238 public:
239     static PassOwnPtr<CodeCache> create() { return adoptPtr(new CodeCache); }
240
241     UnlinkedProgramCodeBlock* getProgramCodeBlock(VM&, ProgramExecutable*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
242     UnlinkedEvalCodeBlock* getEvalCodeBlock(VM&, EvalExecutable*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
243     UnlinkedFunctionExecutable* getFunctionExecutableFromGlobalCode(VM&, const Identifier&, const SourceCode&, ParserError&);
244     ~CodeCache();
245
246     void clear()
247     {
248         m_sourceCode.clear();
249     }
250
251 private:
252     CodeCache();
253
254     template <class UnlinkedCodeBlockType, class ExecutableType> 
255     UnlinkedCodeBlockType* getGlobalCodeBlock(VM&, ExecutableType*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
256
257     CodeCacheMap m_sourceCode;
258 };
259
260 }
261
262 #endif // CodeCache_h