1// Copyright 2017 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#ifndef V8_OBJECTS_HASH_TABLE_H_
6#define V8_OBJECTS_HASH_TABLE_H_
7
8#include "src/base/compiler-specific.h"
9#include "src/base/export-template.h"
10#include "src/base/macros.h"
11#include "src/common/globals.h"
12#include "src/execution/isolate-utils.h"
13#include "src/objects/fixed-array.h"
14#include "src/objects/smi.h"
15#include "src/roots/roots.h"
16
17// Has to be the last include (doesn't have include guards):
18#include "src/objects/object-macros.h"
19
20namespace v8 {
21namespace internal {
22
23namespace third_party_heap {
24class Impl;
25}
26
27// HashTable is a subclass of FixedArray that implements a hash table
28// that uses open addressing and quadratic probing.
29//
30// In order for the quadratic probing to work, elements that have not
31// yet been used and elements that have been deleted are
32// distinguished.  Probing continues when deleted elements are
33// encountered and stops when unused elements are encountered.
34//
35// - Elements with key == undefined have not been used yet.
36// - Elements with key == the_hole have been deleted.
37//
38// The hash table class is parameterized with a Shape.
39// Shape must be a class with the following interface:
40//   class ExampleShape {
41//    public:
42//     // Tells whether key matches other.
43//     static bool IsMatch(Key key, Object other);
44//     // Returns the hash value for key.
45//     static uint32_t Hash(ReadOnlyRoots roots, Key key);
46//     // Returns the hash value for object.
47//     static uint32_t HashForObject(ReadOnlyRoots roots, Object object);
48//     // Convert key to an object.
49//     static inline Handle<Object> AsHandle(Isolate* isolate, Key key);
50//     // The prefix size indicates number of elements in the beginning
51//     // of the backing storage.
52//     static const int kPrefixSize = ..;
53//     // The Element size indicates number of elements per entry.
54//     static const int kEntrySize = ..;
55//     // Indicates whether IsMatch can deal with other being the_hole (a
56//     // deleted entry).
57//     static const bool kMatchNeedsHoleCheck = ..;
58//   };
59// The prefix size indicates an amount of memory in the
60// beginning of the backing storage that can be used for non-element
61// information by subclasses.
62
63template <typename KeyT>
64class V8_EXPORT_PRIVATE BaseShape {
65 public:
66  using Key = KeyT;
67  static Object Unwrap(Object key) { return key; }
68};
69
70class V8_EXPORT_PRIVATE HashTableBase : public NON_EXPORTED_BASE(FixedArray) {
71 public:
72  // Returns the number of elements in the hash table.
73  inline int NumberOfElements() const;
74
75  // Returns the number of deleted elements in the hash table.
76  inline int NumberOfDeletedElements() const;
77
78  // Returns the capacity of the hash table.
79  inline int Capacity() const;
80
81  inline InternalIndex::Range IterateEntries() const;
82
83  // ElementAdded should be called whenever an element is added to a
84  // hash table.
85  inline void ElementAdded();
86
87  // ElementRemoved should be called whenever an element is removed from
88  // a hash table.
89  inline void ElementRemoved();
90  inline void ElementsRemoved(int n);
91
92  // Computes the required capacity for a table holding the given
93  // number of elements. May be more than HashTable::kMaxCapacity.
94  static inline int ComputeCapacity(int at_least_space_for);
95
96  static const int kNumberOfElementsIndex = 0;
97  static const int kNumberOfDeletedElementsIndex = 1;
98  static const int kCapacityIndex = 2;
99  static const int kPrefixStartIndex = 3;
100
101  // Minimum capacity for newly created hash tables.
102  static const int kMinCapacity = 4;
103
104 protected:
105  // Update the number of elements in the hash table.
106  inline void SetNumberOfElements(int nof);
107
108  // Update the number of deleted elements in the hash table.
109  inline void SetNumberOfDeletedElements(int nod);
110
111  // Returns probe entry.
112  inline static InternalIndex FirstProbe(uint32_t hash, uint32_t size) {
113    return InternalIndex(hash & (size - 1));
114  }
115
116  inline static InternalIndex NextProbe(InternalIndex last, uint32_t number,
117                                        uint32_t size) {
118    return InternalIndex((last.as_uint32() + number) & (size - 1));
119  }
120
121  OBJECT_CONSTRUCTORS(HashTableBase, FixedArray);
122};
123
124template <typename Derived, typename Shape>
125class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) HashTable
126    : public HashTableBase {
127 public:
128  using ShapeT = Shape;
129  using Key = typename Shape::Key;
130
131  // Returns a new HashTable object.
132  template <typename IsolateT>
133  V8_WARN_UNUSED_RESULT static Handle<Derived> New(
134      IsolateT* isolate, int at_least_space_for,
135      AllocationType allocation = AllocationType::kYoung,
136      MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY);
137
138  static inline Handle<Map> GetMap(ReadOnlyRoots roots);
139
140  // Garbage collection support.
141  void IteratePrefix(ObjectVisitor* visitor);
142  void IterateElements(ObjectVisitor* visitor);
143
144  // Find entry for key otherwise return kNotFound.
145  inline InternalIndex FindEntry(PtrComprCageBase cage_base,
146                                 ReadOnlyRoots roots, Key key, int32_t hash);
147  template <typename IsolateT>
148  inline InternalIndex FindEntry(IsolateT* isolate, Key key);
149
150  // Rehashes the table in-place.
151  void Rehash(PtrComprCageBase cage_base);
152
153  // Returns whether k is a real key.  The hole and undefined are not allowed as
154  // keys and can be used to indicate missing or deleted elements.
155  static inline bool IsKey(ReadOnlyRoots roots, Object k);
156
157  inline bool ToKey(ReadOnlyRoots roots, InternalIndex entry, Object* out_k);
158  inline bool ToKey(PtrComprCageBase cage_base, InternalIndex entry,
159                    Object* out_k);
160
161  // Returns the key at entry.
162  inline Object KeyAt(InternalIndex entry);
163  inline Object KeyAt(PtrComprCageBase cage_base, InternalIndex entry);
164  inline Object KeyAt(InternalIndex entry, RelaxedLoadTag tag);
165  inline Object KeyAt(PtrComprCageBase cage_base, InternalIndex entry,
166                      RelaxedLoadTag tag);
167
168  static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize;
169  static const int kEntrySize = Shape::kEntrySize;
170  STATIC_ASSERT(kEntrySize > 0);
171  static const int kEntryKeyIndex = 0;
172  static const int kElementsStartOffset =
173      kHeaderSize + kElementsStartIndex * kTaggedSize;
174  // Maximal capacity of HashTable. Based on maximal length of underlying
175  // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex
176  // cannot overflow.
177  static const int kMaxCapacity =
178      (FixedArray::kMaxLength - kElementsStartIndex) / kEntrySize;
179
180  // Don't shrink a HashTable below this capacity.
181  static const int kMinShrinkCapacity = 16;
182
183  // Pretenure hashtables above this capacity.
184  static const int kMinCapacityForPretenure = 256;
185
186  static const int kMaxRegularCapacity = kMaxRegularHeapObjectSize / 32;
187
188  // Returns the index for an entry (of the key)
189  static constexpr inline int EntryToIndex(InternalIndex entry) {
190    return (entry.as_int() * kEntrySize) + kElementsStartIndex;
191  }
192
193  // Returns the entry for an index (of the key)
194  static constexpr inline InternalIndex IndexToEntry(int index) {
195    return InternalIndex((index - kElementsStartIndex) / kEntrySize);
196  }
197
198  // Returns the index for a slot address in the object.
199  static constexpr inline int SlotToIndex(Address object, Address slot) {
200    return static_cast<int>((slot - object - kHeaderSize) / kTaggedSize);
201  }
202
203  // Ensure enough space for n additional elements.
204  template <typename IsolateT>
205  V8_WARN_UNUSED_RESULT static Handle<Derived> EnsureCapacity(
206      IsolateT* isolate, Handle<Derived> table, int n = 1,
207      AllocationType allocation = AllocationType::kYoung);
208
209  // Returns true if this table has sufficient capacity for adding n elements.
210  bool HasSufficientCapacityToAdd(int number_of_additional_elements);
211
212  // Returns true if a table with the given parameters has sufficient capacity
213  // for adding n elements. Can be used to check hypothetical capacities without
214  // actually allocating a table with that capacity.
215  static bool HasSufficientCapacityToAdd(int capacity, int number_of_elements,
216                                         int number_of_deleted_elements,
217                                         int number_of_additional_elements);
218
219 protected:
220  friend class ObjectHashTable;
221
222  template <typename IsolateT>
223  V8_WARN_UNUSED_RESULT static Handle<Derived> NewInternal(
224      IsolateT* isolate, int capacity, AllocationType allocation);
225
226  // Find the entry at which to insert element with the given key that
227  // has the given hash value.
228  InternalIndex FindInsertionEntry(PtrComprCageBase cage_base,
229                                   ReadOnlyRoots roots, uint32_t hash);
230  template <typename IsolateT>
231  InternalIndex FindInsertionEntry(IsolateT* isolate, uint32_t hash);
232
233  // Computes the capacity a table with the given capacity would need to have
234  // room for the given number of elements, also allowing it to shrink.
235  static int ComputeCapacityWithShrink(int current_capacity,
236                                       int at_least_room_for);
237
238  // Shrink the hash table.
239  V8_WARN_UNUSED_RESULT static Handle<Derived> Shrink(
240      Isolate* isolate, Handle<Derived> table, int additionalCapacity = 0);
241
242  // Rehashes this hash-table into the new table.
243  void Rehash(PtrComprCageBase cage_base, Derived new_table);
244
245  inline void set_key(int index, Object value);
246  inline void set_key(int index, Object value, WriteBarrierMode mode);
247
248 private:
249  // Ensure that kMaxRegularCapacity yields a non-large object dictionary.
250  STATIC_ASSERT(EntryToIndex(InternalIndex(kMaxRegularCapacity)) <
251                kMaxRegularLength);
252  STATIC_ASSERT(v8::base::bits::IsPowerOfTwo(kMaxRegularCapacity));
253  static const int kMaxRegularEntry = kMaxRegularCapacity / kEntrySize;
254  static const int kMaxRegularIndex =
255      EntryToIndex(InternalIndex(kMaxRegularEntry));
256  STATIC_ASSERT(OffsetOfElementAt(kMaxRegularIndex) <
257                kMaxRegularHeapObjectSize);
258
259  // Sets the capacity of the hash table.
260  inline void SetCapacity(int capacity);
261
262  // Returns _expected_ if one of entries given by the first _probe_ probes is
263  // equal to  _expected_. Otherwise, returns the entry given by the probe
264  // number _probe_.
265  InternalIndex EntryForProbe(ReadOnlyRoots roots, Object k, int probe,
266                              InternalIndex expected);
267
268  void Swap(InternalIndex entry1, InternalIndex entry2, WriteBarrierMode mode);
269
270  OBJECT_CONSTRUCTORS(HashTable, HashTableBase);
271};
272
273#define EXTERN_DECLARE_HASH_TABLE(DERIVED, SHAPE)                            \
274  extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)           \
275      HashTable<class DERIVED, SHAPE>;                                       \
276                                                                             \
277  extern template EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Handle<DERIVED> \
278  HashTable<DERIVED, SHAPE>::New(Isolate*, int, AllocationType,              \
279                                 MinimumCapacity);                           \
280  extern template EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Handle<DERIVED> \
281  HashTable<DERIVED, SHAPE>::New(LocalIsolate*, int, AllocationType,         \
282                                 MinimumCapacity);                           \
283                                                                             \
284  extern template EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Handle<DERIVED> \
285  HashTable<DERIVED, SHAPE>::EnsureCapacity(Isolate*, Handle<DERIVED>, int,  \
286                                            AllocationType);                 \
287  extern template EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Handle<DERIVED> \
288  HashTable<DERIVED, SHAPE>::EnsureCapacity(LocalIsolate*, Handle<DERIVED>,  \
289                                            int, AllocationType);
290
291// HashTableKey is an abstract superclass for virtual key behavior.
292class HashTableKey {
293 public:
294  explicit HashTableKey(uint32_t hash) : hash_(hash) {}
295
296  // Returns whether the other object matches this key.
297  virtual bool IsMatch(Object other) = 0;
298  // Returns the hash value for this key.
299  // Required.
300  virtual ~HashTableKey() = default;
301
302  uint32_t Hash() const { return hash_; }
303
304 protected:
305  void set_hash(uint32_t hash) {
306    DCHECK_EQ(0, hash_);
307    hash_ = hash;
308  }
309
310 private:
311  uint32_t hash_ = 0;
312};
313
314class ObjectHashTableShape : public BaseShape<Handle<Object>> {
315 public:
316  static inline bool IsMatch(Handle<Object> key, Object other);
317  static inline uint32_t Hash(ReadOnlyRoots roots, Handle<Object> key);
318  static inline uint32_t HashForObject(ReadOnlyRoots roots, Object object);
319  static inline Handle<Object> AsHandle(Handle<Object> key);
320  static const int kPrefixSize = 0;
321  static const int kEntryValueIndex = 1;
322  static const int kEntrySize = 2;
323  static const bool kMatchNeedsHoleCheck = false;
324};
325
326template <typename Derived, typename Shape>
327class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) ObjectHashTableBase
328    : public HashTable<Derived, Shape> {
329 public:
330  // Looks up the value associated with the given key. The hole value is
331  // returned in case the key is not present.
332  Object Lookup(Handle<Object> key);
333  Object Lookup(Handle<Object> key, int32_t hash);
334  Object Lookup(PtrComprCageBase cage_base, Handle<Object> key, int32_t hash);
335
336  // Returns the value at entry.
337  Object ValueAt(InternalIndex entry);
338
339  // Overwrite all keys and values with the hole value.
340  static void FillEntriesWithHoles(Handle<Derived>);
341
342  // Adds (or overwrites) the value associated with the given key.
343  static Handle<Derived> Put(Handle<Derived> table, Handle<Object> key,
344                             Handle<Object> value);
345  static Handle<Derived> Put(Isolate* isolate, Handle<Derived> table,
346                             Handle<Object> key, Handle<Object> value,
347                             int32_t hash);
348
349  // Returns an ObjectHashTable (possibly |table|) where |key| has been removed.
350  static Handle<Derived> Remove(Isolate* isolate, Handle<Derived> table,
351                                Handle<Object> key, bool* was_present);
352  static Handle<Derived> Remove(Isolate* isolate, Handle<Derived> table,
353                                Handle<Object> key, bool* was_present,
354                                int32_t hash);
355
356  // Returns the index to the value of an entry.
357  static inline int EntryToValueIndex(InternalIndex entry) {
358    return HashTable<Derived, Shape>::EntryToIndex(entry) +
359           Shape::kEntryValueIndex;
360  }
361
362 protected:
363  void AddEntry(InternalIndex entry, Object key, Object value);
364  void RemoveEntry(InternalIndex entry);
365
366  OBJECT_CONSTRUCTORS(ObjectHashTableBase, HashTable<Derived, Shape>);
367};
368
369#define EXTERN_DECLARE_OBJECT_BASE_HASH_TABLE(DERIVED, SHAPE)      \
370  EXTERN_DECLARE_HASH_TABLE(DERIVED, SHAPE)                        \
371  extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) \
372      ObjectHashTableBase<class DERIVED, SHAPE>;
373
374EXTERN_DECLARE_OBJECT_BASE_HASH_TABLE(ObjectHashTable, ObjectHashTableShape)
375
376// ObjectHashTable maps keys that are arbitrary objects to object values by
377// using the identity hash of the key for hashing purposes.
378class V8_EXPORT_PRIVATE ObjectHashTable
379    : public ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape> {
380 public:
381  DECL_CAST(ObjectHashTable)
382  DECL_PRINTER(ObjectHashTable)
383
384  OBJECT_CONSTRUCTORS(
385      ObjectHashTable,
386      ObjectHashTableBase<ObjectHashTable, ObjectHashTableShape>);
387};
388
389EXTERN_DECLARE_OBJECT_BASE_HASH_TABLE(EphemeronHashTable, ObjectHashTableShape)
390
391// EphemeronHashTable is similar to ObjectHashTable but gets special treatment
392// by the GC. The GC treats its entries as ephemerons: both key and value are
393// weak references, however if the key is strongly reachable its corresponding
394// value is also kept alive.
395class V8_EXPORT_PRIVATE EphemeronHashTable
396    : public ObjectHashTableBase<EphemeronHashTable, ObjectHashTableShape> {
397 public:
398  static inline Handle<Map> GetMap(ReadOnlyRoots roots);
399
400  DECL_CAST(EphemeronHashTable)
401  DECL_PRINTER(EphemeronHashTable)
402  class BodyDescriptor;
403
404 protected:
405  friend class MarkCompactCollector;
406  friend class ScavengerCollector;
407  friend class third_party_heap::Impl;
408  friend class HashTable<EphemeronHashTable, ObjectHashTableShape>;
409  friend class ObjectHashTableBase<EphemeronHashTable, ObjectHashTableShape>;
410  inline void set_key(int index, Object value);
411  inline void set_key(int index, Object value, WriteBarrierMode mode);
412
413  OBJECT_CONSTRUCTORS(
414      EphemeronHashTable,
415      ObjectHashTableBase<EphemeronHashTable, ObjectHashTableShape>);
416};
417
418class ObjectHashSetShape : public ObjectHashTableShape {
419 public:
420  static const int kPrefixSize = 0;
421  static const int kEntrySize = 1;
422};
423
424EXTERN_DECLARE_HASH_TABLE(ObjectHashSet, ObjectHashSetShape)
425
426class V8_EXPORT_PRIVATE ObjectHashSet
427    : public HashTable<ObjectHashSet, ObjectHashSetShape> {
428 public:
429  static Handle<ObjectHashSet> Add(Isolate* isolate, Handle<ObjectHashSet> set,
430                                   Handle<Object> key);
431
432  inline bool Has(Isolate* isolate, Handle<Object> key, int32_t hash);
433  inline bool Has(Isolate* isolate, Handle<Object> key);
434
435  DECL_CAST(ObjectHashSet)
436
437  OBJECT_CONSTRUCTORS(ObjectHashSet,
438                      HashTable<ObjectHashSet, ObjectHashSetShape>);
439};
440
441class NameToIndexShape : public BaseShape<Handle<Name>> {
442 public:
443  static inline bool IsMatch(Handle<Name> key, Object other);
444  static inline uint32_t Hash(ReadOnlyRoots roots, Handle<Name> key);
445  static inline uint32_t HashForObject(ReadOnlyRoots roots, Object object);
446  static inline Handle<Object> AsHandle(Handle<Name> key);
447  static const int kPrefixSize = 0;
448  static const int kEntryValueIndex = 1;
449  static const int kEntrySize = 2;
450  static const bool kMatchNeedsHoleCheck = false;
451};
452
453class V8_EXPORT_PRIVATE NameToIndexHashTable
454    : public HashTable<NameToIndexHashTable, NameToIndexShape> {
455 public:
456  static const int kEntryValueIndex = NameToIndexShape::kEntryValueIndex;
457
458  inline static Handle<Map> GetMap(ReadOnlyRoots roots);
459  int Lookup(Handle<Name> key);
460
461  // Returns the value at entry.
462  Object ValueAt(InternalIndex entry);
463  int IndexAt(InternalIndex entry);
464
465  template <typename IsolateT>
466  static Handle<NameToIndexHashTable> Add(IsolateT* isolate,
467                                          Handle<NameToIndexHashTable> table,
468                                          Handle<Name> key, int32_t value);
469
470  DECL_CAST(NameToIndexHashTable)
471  DECL_PRINTER(NameToIndexHashTable)
472
473  OBJECT_CONSTRUCTORS(NameToIndexHashTable,
474                      HashTable<NameToIndexHashTable, NameToIndexShape>);
475
476 private:
477  static inline int EntryToValueIndex(InternalIndex entry) {
478    return EntryToIndex(entry) + NameToIndexShape::kEntryValueIndex;
479  }
480};
481
482class RegisteredSymbolTableShape : public BaseShape<Handle<String>> {
483 public:
484  static inline bool IsMatch(Handle<String> key, Object other);
485  static inline uint32_t Hash(ReadOnlyRoots roots, Handle<String> key);
486  static inline uint32_t HashForObject(ReadOnlyRoots roots, Object object);
487  static const int kPrefixSize = 0;
488  static const int kEntryValueIndex = 1;
489  static const int kEntrySize = 2;
490  static const bool kMatchNeedsHoleCheck = false;
491};
492
493class RegisteredSymbolTable
494    : public HashTable<RegisteredSymbolTable, RegisteredSymbolTableShape> {
495 public:
496  Object SlowReverseLookup(Object value);
497
498  // Returns the value at entry.
499  Object ValueAt(InternalIndex entry);
500
501  inline static Handle<Map> GetMap(ReadOnlyRoots roots);
502
503  static Handle<RegisteredSymbolTable> Add(Isolate* isolate,
504                                           Handle<RegisteredSymbolTable> table,
505                                           Handle<String> key, Handle<Symbol>);
506
507  DECL_CAST(RegisteredSymbolTable)
508  DECL_PRINTER(RegisteredSymbolTable)
509  OBJECT_CONSTRUCTORS(
510      RegisteredSymbolTable,
511      HashTable<RegisteredSymbolTable, RegisteredSymbolTableShape>);
512
513 private:
514  static inline int EntryToValueIndex(InternalIndex entry) {
515    return EntryToIndex(entry) + RegisteredSymbolTableShape::kEntryValueIndex;
516  }
517};
518
519}  // namespace internal
520}  // namespace v8
521
522#include "src/objects/object-macros-undef.h"
523
524#endif  // V8_OBJECTS_HASH_TABLE_H_
525