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