1 // Copyright 2021 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_SWISS_NAME_DICTIONARY_H_ 6 #define V8_OBJECTS_SWISS_NAME_DICTIONARY_H_ 7 8 #include <cstdint> 9 10 #include "src/base/export-template.h" 11 #include "src/base/optional.h" 12 #include "src/common/globals.h" 13 #include "src/objects/fixed-array.h" 14 #include "src/objects/internal-index.h" 15 #include "src/objects/js-objects.h" 16 #include "src/objects/swiss-hash-table-helpers.h" 17 #include "src/roots/roots.h" 18 19 // Has to be the last include (doesn't have include guards): 20 #include "src/objects/object-macros.h" 21 22 namespace v8 { 23 namespace internal { 24 25 // A property backing store based on Swiss Tables/Abseil's flat_hash_map. The 26 // implementation is heavily based on Abseil's raw_hash_set.h. 27 // 28 // Memory layout (see below for detailed description of parts): 29 // Prefix: [table type dependent part, can have 0 size] 30 // Capacity: 4 bytes, raw int32_t 31 // Meta table pointer: kTaggedSize bytes 32 // Data table: 2 * |capacity| * |kTaggedSize| bytes 33 // Ctrl table: |capacity| + |kGroupWidth| uint8_t entries 34 // PropertyDetails table: |capacity| uint_8 entries 35 // 36 // Note that because of |kInitialCapacity| == 4 there is no need for padding. 37 // 38 // Description of parts directly contained in SwissNameDictionary allocation: 39 // Prefix: 40 // In case of SwissNameDictionary: 41 // identity hash: 4 bytes, raw int32_t 42 // Meta table pointer: kTaggedSize bytes. 43 // See below for explanation of the meta table. 44 // Data table: 45 // For each logical bucket of the hash table, contains the corresponding key 46 // and value. 47 // Ctrl table: 48 // The control table is used to implement a Swiss Table: Each byte is either 49 // Ctrl::kEmpty, Ctrl::kDeleted, or in case of a bucket denoting a present 50 // entry in the hash table, the 7 lowest bits of the key's hash. The first 51 // |capacity| entries are the actual control table. The additional 52 // |kGroupWidth| bytes contain a copy of the first min(capacity, 53 // kGroupWidth) bytes of the table. 54 // PropertyDetails table: 55 // Each byte contains the PropertyDetails for the corresponding bucket of 56 // the ctrl table. Entries may contain unitialized data if the corresponding 57 // bucket hasn't been used before. 58 // 59 // Meta table: 60 // The meta table (not to be confused with the control table used in any 61 // Swiss Table design!) is a separate ByteArray. Here, the "X" in "uintX_t" 62 // depends on the capacity of the swiss table. For capacities <= 256 we have X 63 // = 8, for 256 < |capacity| <= 2^16 we have X = 16, and otherwise X = 32 (see 64 // MetaTableSizePerEntryFor). It contais the following data: 65 // Number of Entries: uintX_t. 66 // Number of Deleted Entries: uintX_t. 67 // Enumeration table: max_load_factor * Capacity() entries of type uintX_t: 68 // The i-th entry in the enumeration table 69 // contains the number of the bucket representing the i-th entry of the 70 // table in enumeration order. Entries may contain unitialized data if the 71 // corresponding bucket hasn't been used before. 72 class V8_EXPORT_PRIVATE SwissNameDictionary : public HeapObject { 73 public: 74 using Group = swiss_table::Group; 75 76 template <typename IsolateT> 77 inline static Handle<SwissNameDictionary> Add( 78 IsolateT* isolate, Handle<SwissNameDictionary> table, Handle<Name> key, 79 Handle<Object> value, PropertyDetails details, 80 InternalIndex* entry_out = nullptr); 81 82 static Handle<SwissNameDictionary> Shrink(Isolate* isolate, 83 Handle<SwissNameDictionary> table); 84 85 static Handle<SwissNameDictionary> DeleteEntry( 86 Isolate* isolate, Handle<SwissNameDictionary> table, InternalIndex entry); 87 88 template <typename IsolateT> 89 inline InternalIndex FindEntry(IsolateT* isolate, Object key); 90 91 // This is to make the interfaces of NameDictionary::FindEntry and 92 // OrderedNameDictionary::FindEntry compatible. 93 // TODO(emrich) clean this up: NameDictionary uses Handle<Object> 94 // for FindEntry keys due to its Key typedef, but that's also used 95 // for adding, where we do need handles. 96 template <typename IsolateT> 97 inline InternalIndex FindEntry(IsolateT* isolate, Handle<Object> key); 98 99 static inline bool IsKey(ReadOnlyRoots roots, Object key_candidate); 100 inline bool ToKey(ReadOnlyRoots roots, InternalIndex entry, Object* out_key); 101 102 inline Object KeyAt(InternalIndex entry); 103 inline Name NameAt(InternalIndex entry); 104 inline Object ValueAt(InternalIndex entry); 105 // Returns {} if we would be reading out of the bounds of the object. 106 inline base::Optional<Object> TryValueAt(InternalIndex entry); 107 inline PropertyDetails DetailsAt(InternalIndex entry); 108 109 inline void ValueAtPut(InternalIndex entry, Object value); 110 inline void DetailsAtPut(InternalIndex entry, PropertyDetails value); 111 112 inline int NumberOfElements(); 113 inline int NumberOfDeletedElements(); 114 115 inline int Capacity(); 116 inline int UsedCapacity(); 117 118 int NumberOfEnumerableProperties(); 119 120 static Handle<SwissNameDictionary> ShallowCopy( 121 Isolate* isolate, Handle<SwissNameDictionary> table); 122 123 // Strict in the sense that it checks that all used/initialized memory in 124 // |this| and |other| is the same. The only exceptions are the meta table 125 // pointer (which must differ between the two tables) and PropertyDetails of 126 // deleted entries (which reside in initialized memory, but are not compared). 127 bool EqualsForTesting(SwissNameDictionary other); 128 129 template <typename IsolateT> 130 void Initialize(IsolateT* isolate, ByteArray meta_table, int capacity); 131 132 template <typename IsolateT> 133 static Handle<SwissNameDictionary> Rehash(IsolateT* isolate, 134 Handle<SwissNameDictionary> table, 135 int new_capacity); 136 template <typename IsolateT> 137 void Rehash(IsolateT* isolate); 138 139 inline void SetHash(int hash); 140 inline int Hash(); 141 142 Object SlowReverseLookup(Isolate* isolate, Object value); 143 144 class IndexIterator { 145 public: 146 inline IndexIterator(Handle<SwissNameDictionary> dict, int start); 147 148 inline IndexIterator& operator++(); 149 150 inline bool operator==(const IndexIterator& b) const; 151 inline bool operator!=(const IndexIterator& b) const; 152 153 inline InternalIndex operator*(); 154 155 private: 156 int used_capacity_; 157 int enum_index_; 158 159 // This may be an empty handle, but only if the capacity of the table is 160 // 0 and pointer compression is disabled. 161 Handle<SwissNameDictionary> dict_; 162 }; 163 164 class IndexIterable { 165 public: 166 inline explicit IndexIterable(Handle<SwissNameDictionary> dict); 167 168 inline IndexIterator begin(); 169 inline IndexIterator end(); 170 171 private: 172 // This may be an empty handle, but only if the capacity of the table is 173 // 0 and pointer compression is disabled. 174 Handle<SwissNameDictionary> dict_; 175 }; 176 177 inline IndexIterable IterateEntriesOrdered(); 178 inline IndexIterable IterateEntries(); 179 180 // For the given enumeration index, returns the entry (= bucket of the Swiss 181 // Table) containing the data for the mapping with that enumeration index. 182 // The returned bucket may be deleted. 183 inline int EntryForEnumerationIndex(int enumeration_index); 184 185 inline static constexpr bool IsValidCapacity(int capacity); 186 inline static int CapacityFor(int at_least_space_for); 187 188 // Given a capacity, how much of it can we fill before resizing? 189 inline static constexpr int MaxUsableCapacity(int capacity); 190 191 // The maximum allowed capacity for any SwissNameDictionary. 192 inline static constexpr int MaxCapacity(); 193 194 // Returns total size in bytes required for a table of given capacity. 195 inline static constexpr int SizeFor(int capacity); 196 197 inline static constexpr int MetaTableSizePerEntryFor(int capacity); 198 inline static constexpr int MetaTableSizeFor(int capacity); 199 200 inline static constexpr int DataTableSize(int capacity); 201 inline static constexpr int CtrlTableSize(int capacity); 202 203 // Indicates that IterateEntries() returns entries ordered. 204 static constexpr bool kIsOrderedDictionaryType = true; 205 206 // Only used in CSA/Torque, where indices are actual integers. In C++, 207 // InternalIndex::NotFound() is always used instead. 208 static constexpr int kNotFoundSentinel = -1; 209 210 static const int kGroupWidth = Group::kWidth; 211 static const bool kUseSIMD = kGroupWidth == 16; 212 213 class BodyDescriptor; 214 215 // Note that 0 is also a valid capacity. Changing this value to a smaller one 216 // may make some padding necessary in the data layout. 217 static constexpr int kInitialCapacity = kSwissNameDictionaryInitialCapacity; 218 219 // Defines how many kTaggedSize sized values are associcated which each entry 220 // in the data table. 221 static constexpr int kDataTableEntryCount = 2; 222 static constexpr int kDataTableKeyEntryIndex = 0; 223 static constexpr int kDataTableValueEntryIndex = kDataTableKeyEntryIndex + 1; 224 225 // Field indices describing the layout of the meta table: A field index of i 226 // means that the corresponding meta table entry resides at an offset of {i * 227 // sizeof(uintX_t)} bytes from the beginning of the meta table. Here, the X in 228 // uintX_t can be 8, 16, or 32, and depends on the capacity of the overall 229 // SwissNameDictionary. See the section "Meta table" in the comment at the 230 // beginning of the SwissNameDictionary class in this file. 231 static constexpr int kMetaTableElementCountFieldIndex = 0; 232 static constexpr int kMetaTableDeletedElementCountFieldIndex = 1; 233 // Field index of the first entry of the enumeration table (which is part of 234 // the meta table). 235 static constexpr int kMetaTableEnumerationDataStartIndex = 2; 236 237 // The maximum capacity of any SwissNameDictionary whose meta table can use 1 238 // byte per entry. 239 static constexpr int kMax1ByteMetaTableCapacity = (1 << 8); 240 // The maximum capacity of any SwissNameDictionary whose meta table can use 2 241 // bytes per entry. 242 static constexpr int kMax2ByteMetaTableCapacity = (1 << 16); 243 244 // TODO(v8:11388) We would like to use Torque-generated constants here, but 245 // those are currently incorrect. 246 // Offset into the overall table, starting at HeapObject standard fields, 247 // in bytes. This means that the map is stored at offset 0. 248 using Offset = int; 249 inline static constexpr Offset PrefixOffset(); 250 inline static constexpr Offset CapacityOffset(); 251 inline static constexpr Offset MetaTablePointerOffset(); 252 inline static constexpr Offset DataTableStartOffset(); 253 inline static constexpr Offset DataTableEndOffset(int capacity); 254 inline static constexpr Offset CtrlTableStartOffset(int capacity); 255 inline static constexpr Offset PropertyDetailsTableStartOffset(int capacity); 256 257 #if VERIFY_HEAP 258 void SwissNameDictionaryVerify(Isolate* isolate, bool slow_checks); 259 #endif 260 DECL_VERIFIER(SwissNameDictionary) 261 DECL_PRINTER(SwissNameDictionary) 262 DECL_CAST(SwissNameDictionary) 263 OBJECT_CONSTRUCTORS(SwissNameDictionary, HeapObject); 264 265 private: 266 using ctrl_t = swiss_table::ctrl_t; 267 using Ctrl = swiss_table::Ctrl; 268 269 template <typename IsolateT> 270 inline static Handle<SwissNameDictionary> EnsureGrowable( 271 IsolateT* isolate, Handle<SwissNameDictionary> table); 272 273 // Returns table of byte-encoded PropertyDetails (without enumeration index 274 // stored in PropertyDetails). 275 inline uint8_t* PropertyDetailsTable(); 276 277 // Sets key and value to the hole for the given entry. 278 inline void ClearDataTableEntry(Isolate* isolate, int entry); 279 inline void SetKey(int entry, Object key); 280 281 inline void DetailsAtPut(int entry, PropertyDetails value); 282 inline void ValueAtPut(int entry, Object value); 283 284 inline PropertyDetails DetailsAt(int entry); 285 inline Object ValueAtRaw(int entry); 286 inline Object KeyAt(int entry); 287 288 inline bool ToKey(ReadOnlyRoots roots, int entry, Object* out_key); 289 290 inline int FindFirstEmpty(uint32_t hash); 291 // Adds |key| -> (|value|, |details|) as a new mapping to the table, which 292 // must have sufficient room. Returns the entry (= bucket) used by the new 293 // mapping. Does not update the number of present entries or the 294 // enumeration table. 295 inline int AddInternal(Name key, Object value, PropertyDetails details); 296 297 // Use |set_ctrl| for modifications whenever possible, since that function 298 // correctly maintains the copy of the first group at the end of the ctrl 299 // table. 300 inline ctrl_t* CtrlTable(); 301 302 inline static bool IsEmpty(ctrl_t c); 303 inline static bool IsFull(ctrl_t c); 304 inline static bool IsDeleted(ctrl_t c); 305 inline static bool IsEmptyOrDeleted(ctrl_t c); 306 307 // Sets the a control byte, taking the necessary copying of the first group 308 // into account. 309 inline void SetCtrl(int entry, ctrl_t h); 310 inline ctrl_t GetCtrl(int entry); 311 312 inline Object LoadFromDataTable(int entry, int data_offset); 313 inline Object LoadFromDataTable(PtrComprCageBase cage_base, int entry, 314 int data_offset); 315 inline void StoreToDataTable(int entry, int data_offset, Object data); 316 inline void StoreToDataTableNoBarrier(int entry, int data_offset, 317 Object data); 318 319 inline void SetCapacity(int capacity); 320 inline void SetNumberOfElements(int elements); 321 inline void SetNumberOfDeletedElements(int deleted_elements); 322 323 static inline swiss_table::ProbeSequence<Group::kWidth> probe(uint32_t hash, 324 int capacity); 325 326 // Sets that the entry with the given |enumeration_index| is stored at the 327 // given bucket of the data table. 328 inline void SetEntryForEnumerationIndex(int enumeration_index, int entry); 329 330 DECL_ACCESSORS(meta_table, ByteArray) 331 inline void SetMetaTableField(int field_index, int value); 332 inline int GetMetaTableField(int field_index); 333 334 template <typename T> 335 inline static void SetMetaTableField(ByteArray meta_table, int field_index, 336 int value); 337 template <typename T> 338 inline static int GetMetaTableField(ByteArray meta_table, int field_index); 339 }; 340 341 } // namespace internal 342 } // namespace v8 343 344 #endif // V8_OBJECTS_SWISS_NAME_DICTIONARY_H_ 345