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
40namespace JSC {
41
42class EvalExecutable;
43class FunctionBodyNode;
44class Identifier;
45class JSScope;
46class ProgramExecutable;
47class UnlinkedCodeBlock;
48class UnlinkedEvalCodeBlock;
49class UnlinkedFunctionCodeBlock;
50class UnlinkedFunctionExecutable;
51class UnlinkedProgramCodeBlock;
52class VM;
53struct ParserError;
54class SourceCode;
55class SourceProvider;
56
57class SourceCodeKey {
58public:
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 << 2) | 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
99private:
100    SourceCode m_sourceCode;
101    String m_name;
102    unsigned m_flags;
103    unsigned m_hash;
104};
105
106struct 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
112struct SourceCodeKeyHashTraits : SimpleClassHashTraits<SourceCodeKey> {
113    static const bool hasIsEmptyValueFunction = true;
114    static bool isEmptyValue(const SourceCodeKey& sourceCodeKey) { return sourceCodeKey.isNull(); }
115};
116
117struct 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
132class CodeCacheMap {
133public:
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
194private:
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().
237class CodeCache {
238    WTF_MAKE_FAST_ALLOCATED;
239public:
240    static PassOwnPtr<CodeCache> create() { return adoptPtr(new CodeCache); }
241
242    UnlinkedProgramCodeBlock* getProgramCodeBlock(VM&, ProgramExecutable*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
243    UnlinkedEvalCodeBlock* getEvalCodeBlock(VM&, EvalExecutable*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
244    UnlinkedFunctionExecutable* getFunctionExecutableFromGlobalCode(VM&, const Identifier&, const SourceCode&, ParserError&);
245    ~CodeCache();
246
247    void clear()
248    {
249        m_sourceCode.clear();
250    }
251
252private:
253    CodeCache();
254
255    template <class UnlinkedCodeBlockType, class ExecutableType>
256    UnlinkedCodeBlockType* getGlobalCodeBlock(VM&, ExecutableType*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
257
258    CodeCacheMap m_sourceCode;
259};
260
261}
262
263#endif // CodeCache_h
264