Do one lookup per code cache insertion instead of two
[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/FixedArray.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 ProgramExecutable;
46 class UnlinkedCodeBlock;
47 class UnlinkedEvalCodeBlock;
48 class UnlinkedFunctionCodeBlock;
49 class UnlinkedFunctionExecutable;
50 class UnlinkedProgramCodeBlock;
51 class JSGlobalData;
52 struct ParserError;
53 class SourceCode;
54 class SourceProvider;
55
56 class SourceCodeKey {
57 public:
58     enum CodeType { EvalType, ProgramType, FunctionType };
59
60     SourceCodeKey()
61     {
62     }
63
64     SourceCodeKey(const SourceCode& sourceCode, const String& name, CodeType codeType, JSParserStrictness jsParserStrictness)
65         : m_sourceCode(sourceCode)
66         , m_name(name)
67         , m_flags((codeType << 1) | jsParserStrictness)
68         , m_hash(string().impl()->hash())
69     {
70     }
71
72     SourceCodeKey(WTF::HashTableDeletedValueType)
73         : m_sourceCode(WTF::HashTableDeletedValue)
74     {
75     }
76
77     bool isHashTableDeletedValue() const { return m_sourceCode.isHashTableDeletedValue(); }
78
79     unsigned hash() const { return m_hash; }
80
81     size_t length() const { return m_sourceCode.length(); }
82
83     bool isNull() const { return m_sourceCode.isNull(); }
84
85     // To save memory, we compute our string on demand. It's expected that source
86     // providers cache their strings to make this efficient.
87     String string() const { return m_sourceCode.toString(); }
88
89     bool operator==(const SourceCodeKey& other) const
90     {
91         return m_hash == other.m_hash
92             && length() == other.length()
93             && m_flags == other.m_flags
94             && m_name == other.m_name
95             && string() == other.string();
96     }
97
98 private:
99     SourceCode m_sourceCode;
100     String m_name;
101     unsigned m_flags;
102     unsigned m_hash;
103 };
104
105 struct SourceCodeKeyHash {
106     static unsigned hash(const SourceCodeKey& key) { return key.hash(); }
107     static bool equal(const SourceCodeKey& a, const SourceCodeKey& b) { return a == b; }
108     static const bool safeToCompareToEmptyOrDeleted = false;
109 };
110
111 struct SourceCodeKeyHashTraits : SimpleClassHashTraits<SourceCodeKey> {
112     static const bool hasIsEmptyValueFunction = true;
113     static bool isEmptyValue(const SourceCodeKey& sourceCodeKey) { return sourceCodeKey.isNull(); }
114 };
115
116 struct SourceCodeValue {
117     SourceCodeValue()
118     {
119     }
120
121     SourceCodeValue(JSGlobalData& globalData, JSCell* cell, int64_t age)
122         : cell(globalData, cell)
123         , age(age)
124     {
125     }
126
127     Strong<JSCell> cell;
128     int64_t age;
129 };
130
131 class CodeCacheMap {
132 public:
133     typedef HashMap<SourceCodeKey, SourceCodeValue, SourceCodeKeyHash, SourceCodeKeyHashTraits> MapType;
134     typedef MapType::iterator iterator;
135     typedef MapType::AddResult AddResult;
136
137     enum { MinCacheCapacity = 1000000 }; // Size in characters
138
139     CodeCacheMap()
140         : m_size(0)
141         , m_capacity(MinCacheCapacity)
142         , m_age(0)
143     {
144     }
145
146
147     AddResult add(const SourceCodeKey& key, const SourceCodeValue& value)
148     {
149         prune();
150
151         AddResult addResult = m_map.add(key, value);
152         if (addResult.isNewEntry) {
153             m_size += key.length();
154             m_age += key.length();
155             return addResult;
156         }
157
158         int64_t age = m_age - addResult.iterator->value.age;
159         if (age > m_capacity) {
160             // A requested object is older than the cache's capacity. We can
161             // infer that requested objects are subject to high eviction probability,
162             // so we grow the cache to improve our hit rate.
163             m_capacity += recencyBias * oldObjectSamplingMultiplier * key.length();
164         } else if (age < m_capacity / 2) {
165             // A requested object is much younger than the cache's capacity. We can
166             // infer that requested objects are subject to low eviction probability,
167             // so we shrink the cache to save memory.
168             m_capacity -= recencyBias * key.length();
169             if (m_capacity < MinCacheCapacity)
170                 m_capacity = MinCacheCapacity;
171         }
172
173         addResult.iterator->value.age = m_age;
174         m_age += key.length();
175         return addResult;
176     }
177
178     void remove(iterator it)
179     {
180         m_size -= it->key.length();
181         m_map.remove(it);
182     }
183
184     void clear()
185     {
186         m_size = 0;
187         m_age = 0;
188         m_map.clear();
189     }
190
191     int64_t age() { return m_age; }
192
193 private:
194     // This constant factor biases cache capacity toward recent activity. We
195     // want to adapt to changing workloads.
196     static const int64_t recencyBias = 4;
197
198     // This constant factor treats a sampled event for one old object as if it
199     // happened for many old objects. Most old objects are evicted before we can
200     // sample them, so we need to extrapolate from the ones we do sample.
201     static const int64_t oldObjectSamplingMultiplier = 32;
202
203     void pruneSlowCase();
204     void prune()
205     {
206         if (m_size < m_capacity)
207             return;
208         pruneSlowCase();
209     }
210
211     MapType m_map;
212     int64_t m_size;
213     int64_t m_capacity;
214     int64_t m_age;
215 };
216
217 // Caches top-level code such as <script>, eval(), new Function, and JSEvaluateScript().
218 class CodeCache {
219 public:
220     static PassOwnPtr<CodeCache> create() { return adoptPtr(new CodeCache); }
221
222     UnlinkedProgramCodeBlock* getProgramCodeBlock(JSGlobalData&, ProgramExecutable*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
223     UnlinkedEvalCodeBlock* getEvalCodeBlock(JSGlobalData&, EvalExecutable*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
224     UnlinkedFunctionExecutable* getFunctionExecutableFromGlobalCode(JSGlobalData&, const Identifier&, const SourceCode&, ParserError&);
225     ~CodeCache();
226
227     void clear()
228     {
229         m_sourceCode.clear();
230     }
231
232 private:
233     CodeCache();
234
235     template <class UnlinkedCodeBlockType, class ExecutableType> 
236     UnlinkedCodeBlockType* getCodeBlock(JSGlobalData&, ExecutableType*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
237
238     CodeCacheMap m_sourceCode;
239 };
240
241 }
242
243 #endif // CodeCache_h