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