// 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_ #include "src/common/assert-scope.h" #include "src/objects/string.h" #include "src/roots/roots.h" // Has to be the last include (doesn't have include guards): #include "src/objects/object-macros.h" namespace v8 { namespace internal { // A generic key for lookups into the string table, which allows heteromorphic // lookup and on-demand creation of new strings. class StringTableKey { public: virtual ~StringTableKey() = default; inline StringTableKey(uint32_t raw_hash_field, int length); uint32_t raw_hash_field() const { DCHECK_NE(0, raw_hash_field_); return raw_hash_field_; } inline uint32_t hash() const; int length() const { return length_; } protected: inline void set_raw_hash_field(uint32_t raw_hash_field); private: uint32_t raw_hash_field_ = 0; int length_; }; class SeqOneByteString; // StringTable, for internalizing strings. The Lookup methods are designed to be // thread-safe, in combination with GC safepoints. // // The string table layout is defined by its Data implementation class, see // StringTable::Data for details. class V8_EXPORT_PRIVATE StringTable { public: static constexpr Smi empty_element() { return Smi::FromInt(0); } static constexpr Smi deleted_element() { return Smi::FromInt(1); } explicit StringTable(Isolate* isolate); ~StringTable(); int Capacity() const; int NumberOfElements() const; // Find string in the string table. If it is not there yet, it is // added. The return value is the string found. Handle<String> LookupString(Isolate* isolate, Handle<String> key); // 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. template <typename StringTableKey, typename IsolateT> Handle<String> LookupKey(IsolateT* isolate, StringTableKey* key); // {raw_string} must be a tagged String pointer. // 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); void Print(PtrComprCageBase cage_base) const; size_t GetCurrentMemoryUsage() const; // 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); void VerifyIfOwnedBy(Isolate* isolate); private: class Data; Data* EnsureCapacity(PtrComprCageBase cage_base, int additional_elements); std::atomic<Data*> data_; // 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_; Isolate* isolate_; }; // 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; static_assert(base::bits::IsPowerOfTwo(kInitialBlockSize)); static constexpr int kInitialBlockSizeHighestBit = kBitsPerInt - base::bits::CountLeadingZeros32(kInitialBlockSize) - 1; // Initial capacity in the block vector. static constexpr int kInitialBlockVectorCapacity = 4; static constexpr Smi deleted_element() { return Smi::FromInt(0); } explicit StringForwardingTable(Isolate* isolate); ~StringForwardingTable(); inline int Size(); // 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); void IterateElements(RootVisitor* visitor); void Reset(); void UpdateAfterEvacuation(); 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_; }; } // namespace internal } // namespace v8 #include "src/objects/object-macros-undef.h" #endif // V8_OBJECTS_STRING_TABLE_H_