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/FixedArray.h>
  36 #include <wtf/Forward.h>
  37 #include <wtf/PassOwnPtr.h>
  38 #include <wtf/RandomNumber.h>
  39 #include <wtf/text/WTFString.h>
  40
  41 namespace JSC {
  42
  43 class EvalExecutable;
  44 class FunctionBodyNode;
  45 class Identifier;
  46 class JSScope;
  47 class ProgramExecutable;
  48 class UnlinkedCodeBlock;
  49 class UnlinkedEvalCodeBlock;
  50 class UnlinkedFunctionCodeBlock;
  51 class UnlinkedFunctionExecutable;
  52 class UnlinkedProgramCodeBlock;
  53 class VM;
  54 struct ParserError;
  55 class SourceCode;
  56 class SourceProvider;
  57
  58 class SourceCodeKey {
  59 public:
  60     enum CodeType { EvalType, ProgramType, FunctionType };
  61
  62     SourceCodeKey()
  63     {
  64     }
  65
  66     SourceCodeKey(const SourceCode& sourceCode, const String& name, CodeType codeType, JSParserStrictness jsParserStrictness)
  67         : m_sourceCode(sourceCode)
  68         , m_name(name)
  69         , m_flags((codeType << 1) | jsParserStrictness)
  70         , m_hash(string().impl()->hash())
  71     {
  72     }
  73
  74     SourceCodeKey(WTF::HashTableDeletedValueType)
  75         : m_sourceCode(WTF::HashTableDeletedValue)
  76     {
  77     }
  78
  79     bool isHashTableDeletedValue() const { return m_sourceCode.isHashTableDeletedValue(); }
  80
  81     unsigned hash() const { return m_hash; }
  82
  83     size_t length() const { return m_sourceCode.length(); }
  84
  85     bool isNull() const { return m_sourceCode.isNull(); }
  86
  87     // To save memory, we compute our string on demand. It's expected that source
  88     // providers cache their strings to make this efficient.
  89     String string() const { return m_sourceCode.toString(); }
  90
  91     bool operator==(const SourceCodeKey& other) const
  92     {
  93         return m_hash == other.m_hash
  94             && length() == other.length()
  95             && m_flags == other.m_flags
  96             && m_name == other.m_name
  97             && string() == other.string();
  98     }
  99
 100 private:
 101     SourceCode m_sourceCode;
 102     String m_name;
 103     unsigned m_flags;
 104     unsigned m_hash;
 105 };
 106
 107 struct SourceCodeKeyHash {
 108     static unsigned hash(const SourceCodeKey& key) { return key.hash(); }
 109     static bool equal(const SourceCodeKey& a, const SourceCodeKey& b) { return a == b; }
 110     static const bool safeToCompareToEmptyOrDeleted = false;
 111 };
 112
 113 struct SourceCodeKeyHashTraits : SimpleClassHashTraits<SourceCodeKey> {
 114     static const bool hasIsEmptyValueFunction = true;
 115     static bool isEmptyValue(const SourceCodeKey& sourceCodeKey) { return sourceCodeKey.isNull(); }
 116 };
 117
 118 struct SourceCodeValue {
 119     SourceCodeValue()
 120     {
 121     }
 122
 123     SourceCodeValue(VM& vm, JSCell* cell, int64_t age)
 124         : cell(vm, cell)
 125         , age(age)
 126     {
 127     }
 128
 129     Strong<JSCell> cell;
 130     int64_t age;
 131 };
 132
 133 class CodeCacheMap {
 134 public:
 135     typedef HashMap<SourceCodeKey, SourceCodeValue, SourceCodeKeyHash, SourceCodeKeyHashTraits> MapType;
 136     typedef MapType::iterator iterator;
 137     typedef MapType::AddResult AddResult;
 138
 139     CodeCacheMap(int64_t workingSetMaxBytes, size_t workingSetMaxEntries)
 140         : m_size(0)
 141         , m_sizeAtLastPrune(0)
 142         , m_timeAtLastPrune(monotonicallyIncreasingTime())
 143         , m_minCapacity(0)
 144         , m_capacity(0)
 145         , m_age(0)
 146         , m_workingSetMaxBytes(workingSetMaxBytes)
 147         , m_workingSetMaxEntries(workingSetMaxEntries)
 148     {
 149     }
 150
 151     AddResult add(const SourceCodeKey& key, const SourceCodeValue& value)
 152     {
 153         prune();
 154
 155         AddResult addResult = m_map.add(key, value);
 156         if (addResult.isNewEntry) {
 157             m_size += key.length();
 158             m_age += key.length();
 159             return addResult;
 160         }
 161
 162         int64_t age = m_age - addResult.iterator->value.age;
 163         if (age > m_capacity) {
 164             // A requested object is older than the cache's capacity. We can
 165             // infer that requested objects are subject to high eviction probability,
 166             // so we grow the cache to improve our hit rate.
 167             m_capacity += recencyBias * oldObjectSamplingMultiplier * key.length();
 168         } else if (age < m_capacity / 2) {
 169             // A requested object is much younger than the cache's capacity. We can
 170             // infer that requested objects are subject to low eviction probability,
 171             // so we shrink the cache to save memory.
 172             m_capacity -= recencyBias * key.length();
 173             if (m_capacity < m_minCapacity)
 174                 m_capacity = m_minCapacity;
 175         }
 176
 177         addResult.iterator->value.age = m_age;
 178         m_age += key.length();
 179         return addResult;
 180     }
 181
 182     void remove(iterator it)
 183     {
 184         m_size -= it->key.length();
 185         m_map.remove(it);
 186     }
 187
 188     void clear()
 189     {
 190         m_size = 0;
 191         m_age = 0;
 192         m_map.clear();
 193     }
 194
 195     int64_t age() { return m_age; }
 196
 197     static const int64_t globalWorkingSetMaxBytes;
 198     static const size_t globalWorkingSetMaxEntries;
 199
 200     // We have a smaller cap for the per-codeblock CodeCache that approximates the
 201     // linked EvalCodeCache limits, but still allows us to keep large string based
 202     // evals at least partially cached.
 203     static const unsigned nonGlobalWorkingSetScale;
 204     static const int64_t nonGlobalWorkingSetMaxBytes;
 205     static const size_t nonGlobalWorkingSetMaxEntries;
 206
 207 private:
 208     // This constant factor biases cache capacity toward allowing a minimum
 209     // working set to enter the cache before it starts evicting.
 210     static const double workingSetTime;
 211
 212     // This constant factor biases cache capacity toward recent activity. We
 213     // want to adapt to changing workloads.
 214     static const int64_t recencyBias = 4;
 215
 216     // This constant factor treats a sampled event for one old object as if it
 217     // happened for many old objects. Most old objects are evicted before we can
 218     // sample them, so we need to extrapolate from the ones we do sample.
 219     static const int64_t oldObjectSamplingMultiplier = 32;
 220
 221     size_t numberOfEntries() const { return static_cast<size_t>(m_map.size()); }
 222     bool canPruneQuickly() const { return numberOfEntries() < m_workingSetMaxEntries; }
 223
 224     void pruneSlowCase();
 225     void prune()
 226     {
 227         if (m_size <= m_capacity && canPruneQuickly())
 228             return;
 229
 230         if (monotonicallyIncreasingTime() - m_timeAtLastPrune < workingSetTime
 231             && m_size - m_sizeAtLastPrune < m_workingSetMaxBytes
 232             && canPruneQuickly())
 233                 return;
 234
 235         pruneSlowCase();
 236     }
 237
 238     MapType m_map;
 239     int64_t m_size;
 240     int64_t m_sizeAtLastPrune;
 241     double m_timeAtLastPrune;
 242     int64_t m_minCapacity;
 243     int64_t m_capacity;
 244     int64_t m_age;
 245     const int64_t m_workingSetMaxBytes;
 246     const size_t m_workingSetMaxEntries;
 247 };
 248
 249 // Caches top-level code such as <script>, eval(), new Function, and JSEvaluateScript().
 250 class CodeCache : public RefCounted<CodeCache> {
 251 public:
 252     enum CodeCacheKind { GlobalCodeCache, NonGlobalCodeCache };
 253     static PassRefPtr<CodeCache> create(CodeCacheKind kind) { return adoptRef(new CodeCache(kind)); }
 254
 255     UnlinkedProgramCodeBlock* getProgramCodeBlock(VM&, ProgramExecutable*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
 256     UnlinkedEvalCodeBlock* getEvalCodeBlock(VM&, JSScope*, EvalExecutable*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
 257     UnlinkedFunctionExecutable* getFunctionExecutableFromGlobalCode(VM&, const Identifier&, const SourceCode&, ParserError&);
 258     ~CodeCache();
 259
 260     void clear()
 261     {
 262         m_sourceCode.clear();
 263     }
 264
 265 private:
 266     CodeCache(CodeCacheKind);
 267
 268     template <class UnlinkedCodeBlockType, class ExecutableType>
 269     UnlinkedCodeBlockType* getCodeBlock(VM&, JSScope*, ExecutableType*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
 270
 271     template <class UnlinkedCodeBlockType, class ExecutableType>
 272     UnlinkedCodeBlockType* generateBytecode(VM&, JSScope*, ExecutableType*, const SourceCode&, JSParserStrictness, DebuggerMode, ProfilerMode, ParserError&);
 273
 274     CodeCacheMap m_sourceCode;
 275 };
 276
 277 }
 278
 279 #endif // CodeCache_h