1// Copyright 2020 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/objects/compilation-cache-table.h"
6
7#include "src/common/assert-scope.h"
8#include "src/objects/compilation-cache-table-inl.h"
9
10namespace v8 {
11namespace internal {
12
13namespace {
14
15const int kLiteralEntryLength = 2;
16const int kLiteralInitialLength = 2;
17const int kLiteralContextOffset = 0;
18const int kLiteralLiteralsOffset = 1;
19
20// The initial placeholder insertion of the eval cache survives this many GCs.
21const int kHashGenerations = 10;
22
23int SearchLiteralsMapEntry(CompilationCacheTable cache, int cache_entry,
24                           Context native_context) {
25  DisallowGarbageCollection no_gc;
26  DCHECK(native_context.IsNativeContext());
27  Object obj = cache.get(cache_entry);
28
29  // Check that there's no confusion between FixedArray and WeakFixedArray (the
30  // object used to be a FixedArray here).
31  DCHECK(!obj.IsFixedArray());
32  if (obj.IsWeakFixedArray()) {
33    WeakFixedArray literals_map = WeakFixedArray::cast(obj);
34    int length = literals_map.length();
35    for (int i = 0; i < length; i += kLiteralEntryLength) {
36      DCHECK(literals_map.Get(i + kLiteralContextOffset)->IsWeakOrCleared());
37      if (literals_map.Get(i + kLiteralContextOffset) ==
38          HeapObjectReference::Weak(native_context)) {
39        return i;
40      }
41    }
42  }
43  return -1;
44}
45
46void AddToFeedbackCellsMap(Handle<CompilationCacheTable> cache, int cache_entry,
47                           Handle<Context> native_context,
48                           Handle<FeedbackCell> feedback_cell) {
49  Isolate* isolate = native_context->GetIsolate();
50  DCHECK(native_context->IsNativeContext());
51  STATIC_ASSERT(kLiteralEntryLength == 2);
52  Handle<WeakFixedArray> new_literals_map;
53  int entry;
54
55  Object obj = cache->get(cache_entry);
56
57  // Check that there's no confusion between FixedArray and WeakFixedArray (the
58  // object used to be a FixedArray here).
59  DCHECK(!obj.IsFixedArray());
60  if (!obj.IsWeakFixedArray() || WeakFixedArray::cast(obj).length() == 0) {
61    new_literals_map = isolate->factory()->NewWeakFixedArray(
62        kLiteralInitialLength, AllocationType::kOld);
63    entry = 0;
64  } else {
65    Handle<WeakFixedArray> old_literals_map(WeakFixedArray::cast(obj), isolate);
66    entry = SearchLiteralsMapEntry(*cache, cache_entry, *native_context);
67    if (entry >= 0) {
68      // Just set the code of the entry.
69      old_literals_map->Set(entry + kLiteralLiteralsOffset,
70                            HeapObjectReference::Weak(*feedback_cell));
71      return;
72    }
73
74    // Can we reuse an entry?
75    DCHECK_LT(entry, 0);
76    int length = old_literals_map->length();
77    for (int i = 0; i < length; i += kLiteralEntryLength) {
78      if (old_literals_map->Get(i + kLiteralContextOffset)->IsCleared()) {
79        new_literals_map = old_literals_map;
80        entry = i;
81        break;
82      }
83    }
84
85    if (entry < 0) {
86      // Copy old optimized code map and append one new entry.
87      new_literals_map = isolate->factory()->CopyWeakFixedArrayAndGrow(
88          old_literals_map, kLiteralEntryLength);
89      entry = old_literals_map->length();
90    }
91  }
92
93  new_literals_map->Set(entry + kLiteralContextOffset,
94                        HeapObjectReference::Weak(*native_context));
95  new_literals_map->Set(entry + kLiteralLiteralsOffset,
96                        HeapObjectReference::Weak(*feedback_cell));
97
98#ifdef DEBUG
99  for (int i = 0; i < new_literals_map->length(); i += kLiteralEntryLength) {
100    MaybeObject object = new_literals_map->Get(i + kLiteralContextOffset);
101    DCHECK(object->IsCleared() ||
102           object->GetHeapObjectAssumeWeak().IsNativeContext());
103    object = new_literals_map->Get(i + kLiteralLiteralsOffset);
104    DCHECK(object->IsCleared() ||
105           object->GetHeapObjectAssumeWeak().IsFeedbackCell());
106  }
107#endif
108
109  Object old_literals_map = cache->get(cache_entry);
110  if (old_literals_map != *new_literals_map) {
111    cache->set(cache_entry, *new_literals_map);
112  }
113}
114
115FeedbackCell SearchLiteralsMap(CompilationCacheTable cache, int cache_entry,
116                               Context native_context) {
117  FeedbackCell result;
118  int entry = SearchLiteralsMapEntry(cache, cache_entry, native_context);
119  if (entry >= 0) {
120    WeakFixedArray literals_map = WeakFixedArray::cast(cache.get(cache_entry));
121    DCHECK_LE(entry + kLiteralEntryLength, literals_map.length());
122    MaybeObject object = literals_map.Get(entry + kLiteralLiteralsOffset);
123
124    if (!object->IsCleared()) {
125      result = FeedbackCell::cast(object->GetHeapObjectAssumeWeak());
126    }
127  }
128  DCHECK(result.is_null() || result.IsFeedbackCell());
129  return result;
130}
131
132// StringSharedKeys are used as keys in the eval cache.
133class StringSharedKey : public HashTableKey {
134 public:
135  // This tuple unambiguously identifies calls to eval() or
136  // CreateDynamicFunction() (such as through the Function() constructor).
137  // * source is the string passed into eval(). For dynamic functions, this is
138  //   the effective source for the function, some of which is implicitly
139  //   generated.
140  // * shared is the shared function info for the function containing the call
141  //   to eval(). for dynamic functions, shared is the native context closure.
142  // * When positive, position is the position in the source where eval is
143  //   called. When negative, position is the negation of the position in the
144  //   dynamic function's effective source where the ')' ends the parameters.
145  StringSharedKey(Handle<String> source, Handle<SharedFunctionInfo> shared,
146                  LanguageMode language_mode, int position)
147      : HashTableKey(CompilationCacheShape::StringSharedHash(
148            *source, *shared, language_mode, position)),
149        source_(source),
150        shared_(shared),
151        language_mode_(language_mode),
152        position_(position) {}
153
154  // This tuple unambiguously identifies script compilation.
155  StringSharedKey(Handle<String> source, LanguageMode language_mode)
156      : HashTableKey(
157            CompilationCacheShape::StringSharedHash(*source, language_mode)),
158        source_(source),
159        language_mode_(language_mode),
160        position_(kNoSourcePosition) {}
161
162  bool IsMatch(Object other) override {
163    DisallowGarbageCollection no_gc;
164    if (!other.IsFixedArray()) {
165      DCHECK(other.IsNumber());
166      uint32_t other_hash = static_cast<uint32_t>(other.Number());
167      return Hash() == other_hash;
168    }
169    FixedArray other_array = FixedArray::cast(other);
170    DCHECK(other_array.get(0).IsSharedFunctionInfo() ||
171           other_array.get(0) == Smi::zero());
172    Handle<SharedFunctionInfo> shared;
173    if (shared_.ToHandle(&shared)) {
174      if (*shared != other_array.get(0)) return false;
175    } else {
176      if (Smi::zero() != other_array.get(0)) return false;
177    }
178    int language_unchecked = Smi::ToInt(other_array.get(2));
179    DCHECK(is_valid_language_mode(language_unchecked));
180    LanguageMode language_mode = static_cast<LanguageMode>(language_unchecked);
181    if (language_mode != language_mode_) return false;
182    int position = Smi::ToInt(other_array.get(3));
183    if (position != position_) return false;
184    String source = String::cast(other_array.get(1));
185    return source.Equals(*source_);
186  }
187
188  Handle<Object> AsHandle(Isolate* isolate) {
189    Handle<FixedArray> array = isolate->factory()->NewFixedArray(4);
190    Handle<SharedFunctionInfo> shared;
191    if (shared_.ToHandle(&shared)) {
192      array->set(0, *shared);
193    } else {
194      array->set(0, Smi::zero());
195    }
196    array->set(1, *source_);
197    array->set(2, Smi::FromEnum(language_mode_));
198    array->set(3, Smi::FromInt(position_));
199    array->set_map(ReadOnlyRoots(isolate).fixed_cow_array_map());
200    return array;
201  }
202
203 private:
204  Handle<String> source_;
205  MaybeHandle<SharedFunctionInfo> shared_;
206  LanguageMode language_mode_;
207  int position_;
208};
209
210// RegExpKey carries the source and flags of a regular expression as key.
211class RegExpKey : public HashTableKey {
212 public:
213  RegExpKey(Handle<String> string, JSRegExp::Flags flags)
214      : HashTableKey(
215            CompilationCacheShape::RegExpHash(*string, Smi::FromInt(flags))),
216        string_(string),
217        flags_(Smi::FromInt(flags)) {}
218
219  // Rather than storing the key in the hash table, a pointer to the
220  // stored value is stored where the key should be.  IsMatch then
221  // compares the search key to the found object, rather than comparing
222  // a key to a key.
223  bool IsMatch(Object obj) override {
224    FixedArray val = FixedArray::cast(obj);
225    return string_->Equals(String::cast(val.get(JSRegExp::kSourceIndex))) &&
226           (flags_ == val.get(JSRegExp::kFlagsIndex));
227  }
228
229  Handle<String> string_;
230  Smi flags_;
231};
232
233// CodeKey carries the SharedFunctionInfo key associated with a Code
234// object value.
235class CodeKey : public HashTableKey {
236 public:
237  explicit CodeKey(Handle<SharedFunctionInfo> key)
238      : HashTableKey(key->Hash()), key_(key) {}
239
240  bool IsMatch(Object string) override { return *key_ == string; }
241
242  Handle<SharedFunctionInfo> key_;
243};
244
245}  // namespace
246
247MaybeHandle<SharedFunctionInfo> CompilationCacheTable::LookupScript(
248    Handle<CompilationCacheTable> table, Handle<String> src,
249    LanguageMode language_mode, Isolate* isolate) {
250  src = String::Flatten(isolate, src);
251  StringSharedKey key(src, language_mode);
252  InternalIndex entry = table->FindEntry(isolate, &key);
253  if (entry.is_not_found()) return MaybeHandle<SharedFunctionInfo>();
254  int index = EntryToIndex(entry);
255  if (!table->get(index).IsFixedArray()) {
256    return MaybeHandle<SharedFunctionInfo>();
257  }
258  Object obj = table->get(index + 1);
259  if (obj.IsSharedFunctionInfo()) {
260    return handle(SharedFunctionInfo::cast(obj), isolate);
261  }
262  return MaybeHandle<SharedFunctionInfo>();
263}
264
265InfoCellPair CompilationCacheTable::LookupEval(
266    Handle<CompilationCacheTable> table, Handle<String> src,
267    Handle<SharedFunctionInfo> outer_info, Handle<Context> native_context,
268    LanguageMode language_mode, int position) {
269  InfoCellPair empty_result;
270  Isolate* isolate = native_context->GetIsolate();
271  src = String::Flatten(isolate, src);
272
273  StringSharedKey key(src, outer_info, language_mode, position);
274  InternalIndex entry = table->FindEntry(isolate, &key);
275  if (entry.is_not_found()) return empty_result;
276
277  int index = EntryToIndex(entry);
278  if (!table->get(index).IsFixedArray()) return empty_result;
279  Object obj = table->get(index + 1);
280  if (!obj.IsSharedFunctionInfo()) return empty_result;
281
282  STATIC_ASSERT(CompilationCacheShape::kEntrySize == 3);
283  FeedbackCell feedback_cell =
284      SearchLiteralsMap(*table, index + 2, *native_context);
285  return InfoCellPair(isolate, SharedFunctionInfo::cast(obj), feedback_cell);
286}
287
288Handle<Object> CompilationCacheTable::LookupRegExp(Handle<String> src,
289                                                   JSRegExp::Flags flags) {
290  Isolate* isolate = GetIsolate();
291  DisallowGarbageCollection no_gc;
292  RegExpKey key(src, flags);
293  InternalIndex entry = FindEntry(isolate, &key);
294  if (entry.is_not_found()) return isolate->factory()->undefined_value();
295  return Handle<Object>(get(EntryToIndex(entry) + 1), isolate);
296}
297
298Handle<CompilationCacheTable> CompilationCacheTable::PutScript(
299    Handle<CompilationCacheTable> cache, Handle<String> src,
300    LanguageMode language_mode, Handle<SharedFunctionInfo> value,
301    Isolate* isolate) {
302  src = String::Flatten(isolate, src);
303  StringSharedKey key(src, language_mode);
304  Handle<Object> k = key.AsHandle(isolate);
305  cache = EnsureCapacity(isolate, cache);
306  InternalIndex entry = cache->FindInsertionEntry(isolate, key.Hash());
307  cache->set(EntryToIndex(entry), *k);
308  cache->set(EntryToIndex(entry) + 1, *value);
309  cache->ElementAdded();
310  return cache;
311}
312
313Handle<CompilationCacheTable> CompilationCacheTable::PutEval(
314    Handle<CompilationCacheTable> cache, Handle<String> src,
315    Handle<SharedFunctionInfo> outer_info, Handle<SharedFunctionInfo> value,
316    Handle<Context> native_context, Handle<FeedbackCell> feedback_cell,
317    int position) {
318  Isolate* isolate = native_context->GetIsolate();
319  src = String::Flatten(isolate, src);
320  StringSharedKey key(src, outer_info, value->language_mode(), position);
321
322  // This block handles 'real' insertions, i.e. the initial dummy insert
323  // (below) has already happened earlier.
324  {
325    Handle<Object> k = key.AsHandle(isolate);
326    InternalIndex entry = cache->FindEntry(isolate, &key);
327    if (entry.is_found()) {
328      cache->set(EntryToIndex(entry), *k);
329      cache->set(EntryToIndex(entry) + 1, *value);
330      // AddToFeedbackCellsMap may allocate a new sub-array to live in the
331      // entry, but it won't change the cache array. Therefore EntryToIndex
332      // and entry remains correct.
333      STATIC_ASSERT(CompilationCacheShape::kEntrySize == 3);
334      AddToFeedbackCellsMap(cache, EntryToIndex(entry) + 2, native_context,
335                            feedback_cell);
336      // Add hash again even on cache hit to avoid unnecessary cache delay in
337      // case of hash collisions.
338    }
339  }
340
341  // Create a dummy entry to mark that this key has already been inserted once.
342  cache = EnsureCapacity(isolate, cache);
343  InternalIndex entry = cache->FindInsertionEntry(isolate, key.Hash());
344  Handle<Object> k =
345      isolate->factory()->NewNumber(static_cast<double>(key.Hash()));
346  cache->set(EntryToIndex(entry), *k);
347  cache->set(EntryToIndex(entry) + 1, Smi::FromInt(kHashGenerations));
348  cache->ElementAdded();
349  return cache;
350}
351
352Handle<CompilationCacheTable> CompilationCacheTable::PutRegExp(
353    Isolate* isolate, Handle<CompilationCacheTable> cache, Handle<String> src,
354    JSRegExp::Flags flags, Handle<FixedArray> value) {
355  RegExpKey key(src, flags);
356  cache = EnsureCapacity(isolate, cache);
357  InternalIndex entry = cache->FindInsertionEntry(isolate, key.Hash());
358  // We store the value in the key slot, and compare the search key
359  // to the stored value with a custom IsMatch function during lookups.
360  cache->set(EntryToIndex(entry), *value);
361  cache->set(EntryToIndex(entry) + 1, *value);
362  cache->ElementAdded();
363  return cache;
364}
365
366void CompilationCacheTable::Age(Isolate* isolate) {
367  DisallowGarbageCollection no_gc;
368  for (InternalIndex entry : IterateEntries()) {
369    const int entry_index = EntryToIndex(entry);
370    const int value_index = entry_index + 1;
371
372    Object key = get(entry_index);
373    if (key.IsNumber()) {
374      // The ageing mechanism for the initial dummy entry in the eval cache.
375      // The 'key' is the hash represented as a Number. The 'value' is a smi
376      // counting down from kHashGenerations. On reaching zero, the entry is
377      // cleared.
378      // Note: The following static assert only establishes an explicit
379      // connection between initialization- and use-sites of the smi value
380      // field.
381      STATIC_ASSERT(kHashGenerations);
382      const int new_count = Smi::ToInt(get(value_index)) - 1;
383      if (new_count == 0) {
384        RemoveEntry(entry_index);
385      } else {
386        DCHECK_GT(new_count, 0);
387        NoWriteBarrierSet(*this, value_index, Smi::FromInt(new_count));
388      }
389    } else if (key.IsFixedArray()) {
390      // The ageing mechanism for script and eval caches.
391      SharedFunctionInfo info = SharedFunctionInfo::cast(get(value_index));
392      if (info.HasBytecodeArray() && info.GetBytecodeArray(isolate).IsOld()) {
393        RemoveEntry(entry_index);
394      }
395    }
396  }
397}
398
399void CompilationCacheTable::Remove(Object value) {
400  DisallowGarbageCollection no_gc;
401  for (InternalIndex entry : IterateEntries()) {
402    int entry_index = EntryToIndex(entry);
403    int value_index = entry_index + 1;
404    if (get(value_index) == value) {
405      RemoveEntry(entry_index);
406    }
407  }
408}
409
410void CompilationCacheTable::RemoveEntry(int entry_index) {
411  Object the_hole_value = GetReadOnlyRoots().the_hole_value();
412  for (int i = 0; i < kEntrySize; i++) {
413    NoWriteBarrierSet(*this, entry_index + i, the_hole_value);
414  }
415  ElementRemoved();
416}
417
418}  // namespace internal
419}  // namespace v8
420