string-table.h 5.71 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_OBJECTS_STRING_TABLE_H_
#define V8_OBJECTS_STRING_TABLE_H_

8 9
#include "src/common/assert-scope.h"
#include "src/objects/string.h"
10
#include "src/roots/roots.h"
11 12 13 14 15 16 17

// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"

namespace v8 {
namespace internal {

18 19
// A generic key for lookups into the string table, which allows heteromorphic
// lookup and on-demand creation of new strings.
20
class StringTableKey {
21
 public:
22
  virtual ~StringTableKey() = default;
23
  inline StringTableKey(uint32_t raw_hash_field, int length);
24

25 26 27
  uint32_t raw_hash_field() const {
    DCHECK_NE(0, raw_hash_field_);
    return raw_hash_field_;
28
  }
29

30 31 32
  inline uint32_t hash() const;
  int length() const { return length_; }

33
 protected:
34
  inline void set_raw_hash_field(uint32_t raw_hash_field);
35 36

 private:
37
  uint32_t raw_hash_field_ = 0;
38
  int length_;
39 40
};

41 42
class SeqOneByteString;

43 44
// StringTable, for internalizing strings. The Lookup methods are designed to be
// thread-safe, in combination with GC safepoints.
45
//
46 47 48
// The string table layout is defined by its Data implementation class, see
// StringTable::Data for details.
class V8_EXPORT_PRIVATE StringTable {
49
 public:
50 51 52
  static constexpr Smi empty_element() { return Smi::FromInt(0); }
  static constexpr Smi deleted_element() { return Smi::FromInt(1); }

53
  explicit StringTable(Isolate* isolate);
54 55 56 57
  ~StringTable();

  int Capacity() const;
  int NumberOfElements() const;
58

59 60
  // Find string in the string table. If it is not there yet, it is
  // added. The return value is the string found.
61
  Handle<String> LookupString(Isolate* isolate, Handle<String> key);
62

63 64 65
  // Find string in the string table, using the given key. If the string is not
  // there yet, it is created (by the key) and added. The return value is the
  // string found.
66 67
  template <typename StringTableKey, typename IsolateT>
  Handle<String> LookupKey(IsolateT* isolate, StringTableKey* key);
68

69
  // {raw_string} must be a tagged String pointer.
70 71 72 73
  // Returns a tagged pointer: either a Smi if the string is an array index, an
  // internalized string, or a Smi sentinel.
  static Address TryStringToIndexOrLookupExisting(Isolate* isolate,
                                                  Address raw_string);
74

75
  void Print(PtrComprCageBase cage_base) const;
76
  size_t GetCurrentMemoryUsage() const;
77

78 79 80 81 82
  // The following methods must be called either while holding the write lock,
  // or while in a Heap safepoint.
  void IterateElements(RootVisitor* visitor);
  void DropOldData();
  void NotifyElementsRemoved(int count);
83

84 85
  void VerifyIfOwnedBy(Isolate* isolate);

86
 private:
87
  class Data;
88

89
  Data* EnsureCapacity(PtrComprCageBase cage_base, int additional_elements);
90 91

  std::atomic<Data*> data_;
92 93 94
  // Write mutex is mutable so that readers of concurrently mutated values (e.g.
  // NumberOfElements) are allowed to lock it while staying const.
  mutable base::Mutex write_mutex_;
95
  Isolate* isolate_;
96 97
};

98 99 100 101 102 103 104 105 106 107 108
// Mapping from forwarding indices (stored in a string's hash field) to
// internalized strings.
// The table is organised in "blocks". As writes only append new entries, the
// organisation in blocks allows lock-free writes. We need a lock only for
// growing the table (adding more blocks). When the vector holding the blocks
// needs to grow, we keep a copy of the old vector alive to allow concurrent
// reads while the vector is relocated.
class StringForwardingTable {
 public:
  // Capacity for the first block.
  static constexpr int kInitialBlockSize = 16;
109
  static_assert(base::bits::IsPowerOfTwo(kInitialBlockSize));
110 111 112 113
  static constexpr int kInitialBlockSizeHighestBit =
      kBitsPerInt - base::bits::CountLeadingZeros32(kInitialBlockSize) - 1;
  // Initial capacity in the block vector.
  static constexpr int kInitialBlockVectorCapacity = 4;
114
  static constexpr Smi deleted_element() { return Smi::FromInt(0); }
115 116 117 118

  explicit StringForwardingTable(Isolate* isolate);
  ~StringForwardingTable();

119
  inline int Size() const;
120 121 122 123
  // Returns the index of the added string pair.
  int Add(Isolate* isolate, String string, String forward_to);
  String GetForwardString(Isolate* isolate, int index) const;
  static Address GetForwardStringAddress(Isolate* isolate, int index);
124 125
  void IterateElements(RootVisitor* visitor);
  void Reset();
126
  void UpdateAfterEvacuation();
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156

 private:
  class Block;
  class BlockVector;

  // Returns the block for a given index and sets the index within this block
  // as out parameter.
  static inline uint32_t BlockForIndex(int index, uint32_t* index_in_block_out);
  static inline uint32_t IndexInBlock(int index, uint32_t block);
  static inline uint32_t CapacityForBlock(uint32_t block);

  void InitializeBlockVector();
  // Ensure that |block| exists in the BlockVector already. If not, a new block
  // is created (with capacity double the capacity of the last block) and
  // inserted into the BlockVector. The BlockVector itself might grow (to double
  // the capacity).
  BlockVector* EnsureCapacity(uint32_t block);

  Isolate* isolate_;
  std::atomic<BlockVector*> blocks_;
  // We need a vector of BlockVectors to keep old BlockVectors alive when we
  // grow the table, due to concurrent reads that may still hold a pointer to
  // them. |block_vector_sotrage_| is only accessed while we grow with the mutex
  // held. All regular access go through |block_|, which holds a pointer to the
  // current BlockVector.
  std::vector<std::unique_ptr<BlockVector>> block_vector_storage_;
  std::atomic<int> next_free_index_;
  base::Mutex grow_mutex_;
};

157 158 159 160 161 162
}  // namespace internal
}  // namespace v8

#include "src/objects/object-macros-undef.h"

#endif  // V8_OBJECTS_STRING_TABLE_H_