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/string-table.h"
6
7 #include <atomic>
8
9 #include "src/base/atomicops.h"
10 #include "src/base/macros.h"
11 #include "src/common/assert-scope.h"
12 #include "src/common/globals.h"
13 #include "src/common/ptr-compr-inl.h"
14 #include "src/execution/isolate-utils-inl.h"
15 #include "src/heap/safepoint.h"
16 #include "src/objects/internal-index.h"
17 #include "src/objects/object-list-macros.h"
18 #include "src/objects/slots-inl.h"
19 #include "src/objects/slots.h"
20 #include "src/objects/string-inl.h"
21 #include "src/objects/string-table-inl.h"
22 #include "src/snapshot/deserializer.h"
23 #include "src/utils/allocation.h"
24 #include "src/utils/ostreams.h"
25
26 namespace v8 {
27 namespace internal {
28
29 namespace {
30
31 static constexpr int kStringTableMaxEmptyFactor = 4;
32 static constexpr int kStringTableMinCapacity = 2048;
33
StringTableHasSufficientCapacityToAdd(int capacity,int number_of_elements,int number_of_deleted_elements,int number_of_additional_elements)34 bool StringTableHasSufficientCapacityToAdd(int capacity, int number_of_elements,
35 int number_of_deleted_elements,
36 int number_of_additional_elements) {
37 int nof = number_of_elements + number_of_additional_elements;
38 // Return true if:
39 // 50% is still free after adding number_of_additional_elements elements and
40 // at most 50% of the free elements are deleted elements.
41 if ((nof < capacity) &&
42 ((number_of_deleted_elements <= (capacity - nof) / 2))) {
43 int needed_free = nof / 2;
44 if (nof + needed_free <= capacity) return true;
45 }
46 return false;
47 }
48
ComputeStringTableCapacity(int at_least_space_for)49 int ComputeStringTableCapacity(int at_least_space_for) {
50 // Add 50% slack to make slot collisions sufficiently unlikely.
51 // See matching computation in StringTableHasSufficientCapacityToAdd().
52 int raw_capacity = at_least_space_for + (at_least_space_for >> 1);
53 int capacity = base::bits::RoundUpToPowerOfTwo32(raw_capacity);
54 return std::max(capacity, kStringTableMinCapacity);
55 }
56
ComputeStringTableCapacityWithShrink(int current_capacity,int at_least_room_for)57 int ComputeStringTableCapacityWithShrink(int current_capacity,
58 int at_least_room_for) {
59 // Only shrink if the table is very empty to avoid performance penalty.
60 DCHECK_GE(current_capacity, kStringTableMinCapacity);
61 if (at_least_room_for > (current_capacity / kStringTableMaxEmptyFactor))
62 return current_capacity;
63
64 // Recalculate the smaller capacity actually needed.
65 int new_capacity = ComputeStringTableCapacity(at_least_room_for);
66 DCHECK_GE(new_capacity, at_least_room_for);
67 // Don't go lower than room for {kStringTableMinCapacity} elements.
68 if (new_capacity < kStringTableMinCapacity) return current_capacity;
69 return new_capacity;
70 }
71
72 template <typename StringTableKey>
KeyIsMatch(StringTableKey * key,String string)73 bool KeyIsMatch(StringTableKey* key, String string) {
74 if (string.hash_field() != key->hash_field()) return false;
75 if (string.length() != key->length()) return false;
76 return key->IsMatch(string);
77 }
78
79 } // namespace
80
81 // Data holds the actual data of the string table, including capacity and number
82 // of elements.
83 //
84 // It is a variable sized structure, with a "header" followed directly in memory
85 // by the elements themselves. These are accessed as offsets from the elements_
86 // field, which itself provides storage for the first element.
87 //
88 // The elements themselves are stored as an open-addressed hash table, with
89 // quadratic probing and Smi 0 and Smi 1 as the empty and deleted sentinels,
90 // respectively.
91 class StringTable::Data {
92 public:
93 static std::unique_ptr<Data> New(int capacity);
94 static std::unique_ptr<Data> Resize(IsolateRoot isolate,
95 std::unique_ptr<Data> data, int capacity);
96
slot(InternalIndex index) const97 OffHeapObjectSlot slot(InternalIndex index) const {
98 return OffHeapObjectSlot(&elements_[index.as_uint32()]);
99 }
100
Get(IsolateRoot isolate,InternalIndex index) const101 Object Get(IsolateRoot isolate, InternalIndex index) const {
102 return slot(index).Acquire_Load(isolate);
103 }
104
Set(InternalIndex index,String entry)105 void Set(InternalIndex index, String entry) {
106 slot(index).Release_Store(entry);
107 }
108
ElementAdded()109 void ElementAdded() {
110 DCHECK_LT(number_of_elements_ + 1, capacity());
111 DCHECK(StringTableHasSufficientCapacityToAdd(
112 capacity(), number_of_elements(), number_of_deleted_elements(), 1));
113
114 number_of_elements_++;
115 }
DeletedElementOverwritten()116 void DeletedElementOverwritten() {
117 DCHECK_LT(number_of_elements_ + 1, capacity());
118 DCHECK(StringTableHasSufficientCapacityToAdd(
119 capacity(), number_of_elements(), number_of_deleted_elements() - 1, 1));
120
121 number_of_elements_++;
122 number_of_deleted_elements_--;
123 }
ElementsRemoved(int count)124 void ElementsRemoved(int count) {
125 DCHECK_LE(count, number_of_elements_);
126 number_of_elements_ -= count;
127 number_of_deleted_elements_ += count;
128 }
129
130 void* operator new(size_t size, int capacity);
131 void* operator new(size_t size) = delete;
132 void operator delete(void* description);
133
capacity() const134 int capacity() const { return capacity_; }
number_of_elements() const135 int number_of_elements() const { return number_of_elements_; }
number_of_deleted_elements() const136 int number_of_deleted_elements() const { return number_of_deleted_elements_; }
137
138 template <typename StringTableKey>
139 InternalIndex FindEntry(IsolateRoot isolate, StringTableKey* key,
140 uint32_t hash) const;
141
142 InternalIndex FindInsertionEntry(IsolateRoot isolate, uint32_t hash) const;
143
144 template <typename StringTableKey>
145 InternalIndex FindEntryOrInsertionEntry(IsolateRoot isolate,
146 StringTableKey* key,
147 uint32_t hash) const;
148
149 // Helper method for StringTable::TryStringToIndexOrLookupExisting.
150 template <typename Char>
151 static Address TryStringToIndexOrLookupExisting(Isolate* isolate,
152 String string, String source,
153 size_t start);
154
155 void IterateElements(RootVisitor* visitor);
156
PreviousData()157 Data* PreviousData() { return previous_data_.get(); }
DropPreviousData()158 void DropPreviousData() { previous_data_.reset(); }
159
160 void Print(IsolateRoot isolate) const;
161 size_t GetCurrentMemoryUsage() const;
162
163 private:
164 explicit Data(int capacity);
165
166 // Returns probe entry.
FirstProbe(uint32_t hash,uint32_t size)167 inline static InternalIndex FirstProbe(uint32_t hash, uint32_t size) {
168 return InternalIndex(hash & (size - 1));
169 }
170
NextProbe(InternalIndex last,uint32_t number,uint32_t size)171 inline static InternalIndex NextProbe(InternalIndex last, uint32_t number,
172 uint32_t size) {
173 return InternalIndex((last.as_uint32() + number) & (size - 1));
174 }
175
176 private:
177 std::unique_ptr<Data> previous_data_;
178 int number_of_elements_;
179 int number_of_deleted_elements_;
180 const int capacity_;
181 Tagged_t elements_[1];
182 };
183
operator new(size_t size,int capacity)184 void* StringTable::Data::operator new(size_t size, int capacity) {
185 // Make sure the size given is the size of the Data structure.
186 DCHECK_EQ(size, sizeof(StringTable::Data));
187 // Make sure that the elements_ array is at the end of Data, with no padding,
188 // so that subsequent elements can be accessed as offsets from elements_.
189 STATIC_ASSERT(offsetof(StringTable::Data, elements_) ==
190 sizeof(StringTable::Data) - sizeof(Tagged_t));
191 // Make sure that elements_ is aligned when StringTable::Data is aligned.
192 STATIC_ASSERT(
193 (alignof(StringTable::Data) + offsetof(StringTable::Data, elements_)) %
194 kTaggedSize ==
195 0);
196
197 // Subtract 1 from capacity, as the member elements_ already supplies the
198 // storage for the first element.
199 return AlignedAlloc(size + (capacity - 1) * sizeof(Tagged_t),
200 alignof(StringTable::Data));
201 }
202
operator delete(void * table)203 void StringTable::Data::operator delete(void* table) { AlignedFree(table); }
204
GetCurrentMemoryUsage() const205 size_t StringTable::Data::GetCurrentMemoryUsage() const {
206 size_t usage = sizeof(*this) + (capacity_ - 1) * sizeof(Tagged_t);
207 if (previous_data_) {
208 usage += previous_data_->GetCurrentMemoryUsage();
209 }
210 return usage;
211 }
212
Data(int capacity)213 StringTable::Data::Data(int capacity)
214 : previous_data_(nullptr),
215 number_of_elements_(0),
216 number_of_deleted_elements_(0),
217 capacity_(capacity) {
218 OffHeapObjectSlot first_slot = slot(InternalIndex(0));
219 MemsetTagged(first_slot, empty_element(), capacity);
220 }
221
New(int capacity)222 std::unique_ptr<StringTable::Data> StringTable::Data::New(int capacity) {
223 return std::unique_ptr<Data>(new (capacity) Data(capacity));
224 }
225
Resize(IsolateRoot isolate,std::unique_ptr<Data> data,int capacity)226 std::unique_ptr<StringTable::Data> StringTable::Data::Resize(
227 IsolateRoot isolate, std::unique_ptr<Data> data, int capacity) {
228 std::unique_ptr<Data> new_data(new (capacity) Data(capacity));
229
230 DCHECK_LT(data->number_of_elements(), new_data->capacity());
231 DCHECK(StringTableHasSufficientCapacityToAdd(
232 new_data->capacity(), new_data->number_of_elements(),
233 new_data->number_of_deleted_elements(), data->number_of_elements()));
234
235 // Rehash the elements.
236 for (InternalIndex i : InternalIndex::Range(data->capacity())) {
237 Object element = data->Get(isolate, i);
238 if (element == empty_element() || element == deleted_element()) continue;
239 String string = String::cast(element);
240 uint32_t hash = string.Hash();
241 InternalIndex insertion_index = new_data->FindInsertionEntry(isolate, hash);
242 new_data->Set(insertion_index, string);
243 }
244 new_data->number_of_elements_ = data->number_of_elements();
245
246 new_data->previous_data_ = std::move(data);
247 return new_data;
248 }
249
250 template <typename StringTableKey>
FindEntry(IsolateRoot isolate,StringTableKey * key,uint32_t hash) const251 InternalIndex StringTable::Data::FindEntry(IsolateRoot isolate,
252 StringTableKey* key,
253 uint32_t hash) const {
254 uint32_t count = 1;
255 // EnsureCapacity will guarantee the hash table is never full.
256 DCHECK_LT(number_of_elements_, capacity_);
257 for (InternalIndex entry = FirstProbe(hash, capacity_);;
258 entry = NextProbe(entry, count++, capacity_)) {
259 // TODO(leszeks): Consider delaying the decompression until after the
260 // comparisons against empty/deleted.
261 Object element = Get(isolate, entry);
262 if (element == empty_element()) return InternalIndex::NotFound();
263 if (element == deleted_element()) continue;
264 String string = String::cast(element);
265 if (KeyIsMatch(key, string)) return entry;
266 }
267 }
268
FindInsertionEntry(IsolateRoot isolate,uint32_t hash) const269 InternalIndex StringTable::Data::FindInsertionEntry(IsolateRoot isolate,
270 uint32_t hash) const {
271 uint32_t count = 1;
272 // EnsureCapacity will guarantee the hash table is never full.
273 DCHECK_LT(number_of_elements_, capacity_);
274 for (InternalIndex entry = FirstProbe(hash, capacity_);;
275 entry = NextProbe(entry, count++, capacity_)) {
276 // TODO(leszeks): Consider delaying the decompression until after the
277 // comparisons against empty/deleted.
278 Object element = Get(isolate, entry);
279 if (element == empty_element() || element == deleted_element())
280 return entry;
281 }
282 }
283
284 template <typename StringTableKey>
FindEntryOrInsertionEntry(IsolateRoot isolate,StringTableKey * key,uint32_t hash) const285 InternalIndex StringTable::Data::FindEntryOrInsertionEntry(
286 IsolateRoot isolate, StringTableKey* key, uint32_t hash) const {
287 InternalIndex insertion_entry = InternalIndex::NotFound();
288 uint32_t count = 1;
289 // EnsureCapacity will guarantee the hash table is never full.
290 DCHECK_LT(number_of_elements_, capacity_);
291 for (InternalIndex entry = FirstProbe(hash, capacity_);;
292 entry = NextProbe(entry, count++, capacity_)) {
293 // TODO(leszeks): Consider delaying the decompression until after the
294 // comparisons against empty/deleted.
295 Object element = Get(isolate, entry);
296 if (element == empty_element()) {
297 // Empty entry, it's our insertion entry if there was no previous Hole.
298 if (insertion_entry.is_not_found()) return entry;
299 return insertion_entry;
300 }
301
302 if (element == deleted_element()) {
303 // Holes are potential insertion candidates, but we continue the search
304 // in case we find the actual matching entry.
305 if (insertion_entry.is_not_found()) insertion_entry = entry;
306 continue;
307 }
308
309 String string = String::cast(element);
310 if (KeyIsMatch(key, string)) return entry;
311 }
312 }
313
IterateElements(RootVisitor * visitor)314 void StringTable::Data::IterateElements(RootVisitor* visitor) {
315 OffHeapObjectSlot first_slot = slot(InternalIndex(0));
316 OffHeapObjectSlot end_slot = slot(InternalIndex(capacity_));
317 visitor->VisitRootPointers(Root::kStringTable, nullptr, first_slot, end_slot);
318 }
319
Print(IsolateRoot isolate) const320 void StringTable::Data::Print(IsolateRoot isolate) const {
321 OFStream os(stdout);
322 os << "StringTable {" << std::endl;
323 for (InternalIndex i : InternalIndex::Range(capacity_)) {
324 os << " " << i.as_uint32() << ": " << Brief(Get(isolate, i)) << std::endl;
325 }
326 os << "}" << std::endl;
327 }
328
StringTable(Isolate * isolate)329 StringTable::StringTable(Isolate* isolate)
330 : data_(Data::New(kStringTableMinCapacity).release())
331 #ifdef DEBUG
332 ,
333 isolate_(isolate)
334 #endif
335 {
336 }
~StringTable()337 StringTable::~StringTable() { delete data_; }
338
Capacity() const339 int StringTable::Capacity() const {
340 return data_.load(std::memory_order_acquire)->capacity();
341 }
NumberOfElements() const342 int StringTable::NumberOfElements() const {
343 {
344 base::MutexGuard table_write_guard(&write_mutex_);
345 return data_.load(std::memory_order_relaxed)->number_of_elements();
346 }
347 }
348
349 // InternalizedStringKey carries a string/internalized-string object as key.
350 class InternalizedStringKey final : public StringTableKey {
351 public:
InternalizedStringKey(Handle<String> string)352 explicit InternalizedStringKey(Handle<String> string)
353 : StringTableKey(0, string->length()), string_(string) {
354 DCHECK(!string->IsInternalizedString());
355 DCHECK(string->IsFlat());
356 // Make sure hash_field is computed.
357 string->Hash();
358 set_hash_field(string->hash_field());
359 }
360
IsMatch(String string)361 bool IsMatch(String string) override {
362 DCHECK(!SharedStringAccessGuardIfNeeded::IsNeeded(string));
363 return string_->SlowEquals(string);
364 }
365
AsHandle(Isolate * isolate)366 Handle<String> AsHandle(Isolate* isolate) {
367 // Internalize the string if possible.
368 MaybeHandle<Map> maybe_map =
369 isolate->factory()->InternalizedStringMapForString(string_);
370 Handle<Map> map;
371 if (maybe_map.ToHandle(&map)) {
372 string_->set_map_no_write_barrier(*map);
373 DCHECK(string_->IsInternalizedString());
374 return string_;
375 }
376 if (FLAG_thin_strings) {
377 // External strings get special treatment, to avoid copying their
378 // contents.
379 if (string_->IsExternalOneByteString()) {
380 return isolate->factory()
381 ->InternalizeExternalString<ExternalOneByteString>(string_);
382 } else if (string_->IsExternalTwoByteString()) {
383 return isolate->factory()
384 ->InternalizeExternalString<ExternalTwoByteString>(string_);
385 }
386 }
387 // Otherwise allocate a new internalized string.
388 return isolate->factory()->NewInternalizedStringImpl(
389 string_, string_->length(), string_->hash_field());
390 }
391
392 private:
393 Handle<String> string_;
394 };
395
LookupString(Isolate * isolate,Handle<String> string)396 Handle<String> StringTable::LookupString(Isolate* isolate,
397 Handle<String> string) {
398 string = String::Flatten(isolate, string);
399 if (string->IsInternalizedString()) return string;
400
401 InternalizedStringKey key(string);
402 Handle<String> result = LookupKey(isolate, &key);
403
404 if (FLAG_thin_strings) {
405 if (!string->IsInternalizedString()) {
406 string->MakeThin(isolate, *result);
407 }
408 } else { // !FLAG_thin_strings
409 if (string->IsConsString()) {
410 Handle<ConsString> cons = Handle<ConsString>::cast(string);
411 cons->set_first(*result);
412 cons->set_second(ReadOnlyRoots(isolate).empty_string());
413 } else if (string->IsSlicedString()) {
414 STATIC_ASSERT(static_cast<int>(ConsString::kSize) ==
415 static_cast<int>(SlicedString::kSize));
416 DisallowHeapAllocation no_gc;
417 bool one_byte = result->IsOneByteRepresentation();
418 Handle<Map> map = one_byte
419 ? isolate->factory()->cons_one_byte_string_map()
420 : isolate->factory()->cons_string_map();
421 string->set_map(*map);
422 Handle<ConsString> cons = Handle<ConsString>::cast(string);
423 cons->set_first(*result);
424 cons->set_second(ReadOnlyRoots(isolate).empty_string());
425 }
426 }
427 return result;
428 }
429
430 template <typename StringTableKey, typename LocalIsolate>
LookupKey(LocalIsolate * isolate,StringTableKey * key)431 Handle<String> StringTable::LookupKey(LocalIsolate* isolate,
432 StringTableKey* key) {
433 // String table lookups are allowed to be concurrent, assuming that:
434 //
435 // - The Heap access is allowed to be concurrent (using LocalHeap or
436 // similar),
437 // - All writes to the string table are guarded by the Isolate string table
438 // mutex,
439 // - Resizes of the string table first copies the old contents to the new
440 // table, and only then sets the new string table pointer to the new
441 // table,
442 // - Only GCs can remove elements from the string table.
443 //
444 // These assumptions allow us to make the following statement:
445 //
446 // "Reads are allowed when not holding the lock, as long as false negatives
447 // (misses) are ok. We will never get a false positive (hit of an entry no
448 // longer in the table)"
449 //
450 // This is because we _know_ that if we find an entry in the string table, any
451 // entry will also be in all reallocations of that tables. This is required
452 // for strong consistency of internalized string equality implying reference
453 // equality.
454 //
455 // We therefore try to optimistically read from the string table without
456 // taking the lock (both here and in the NoAllocate version of the lookup),
457 // and on a miss we take the lock and try to write the entry, with a second
458 // read lookup in case the non-locked read missed a write.
459 //
460 // One complication is allocation -- we don't want to allocate while holding
461 // the string table lock. This applies to both allocation of new strings, and
462 // re-allocation of the string table on resize. So, we optimistically allocate
463 // (without copying values) outside the lock, and potentially discard the
464 // allocation if another write also did an allocation. This assumes that
465 // writes are rarer than reads.
466
467 Handle<String> new_string;
468 while (true) {
469 // Load the current string table data, in case another thread updates the
470 // data while we're reading.
471 const Data* data = data_.load(std::memory_order_acquire);
472
473 // First try to find the string in the table. This is safe to do even if the
474 // table is now reallocated; we won't find a stale entry in the old table
475 // because the new table won't delete it's corresponding entry until the
476 // string is dead, in which case it will die in this table too and worst
477 // case we'll have a false miss.
478 InternalIndex entry = data->FindEntry(isolate, key, key->hash());
479 if (entry.is_found()) {
480 return handle(String::cast(data->Get(isolate, entry)), isolate);
481 }
482
483 // No entry found, so adding new string.
484
485 // Allocate the string before the first insertion attempt, reuse this
486 // allocated value on insertion retries. If another thread concurrently
487 // allocates the same string, the insert will fail, the lookup above will
488 // succeed, and this string will be discarded.
489 if (new_string.is_null()) new_string = key->AsHandle(isolate);
490
491 {
492 base::MutexGuard table_write_guard(&write_mutex_);
493
494 Data* data = EnsureCapacity(isolate, 1);
495
496 // Check one last time if the key is present in the table, in case it was
497 // added after the check.
498 InternalIndex entry =
499 data->FindEntryOrInsertionEntry(isolate, key, key->hash());
500
501 Object element = data->Get(isolate, entry);
502 if (element == empty_element()) {
503 // This entry is empty, so write it and register that we added an
504 // element.
505 data->Set(entry, *new_string);
506 data->ElementAdded();
507 return new_string;
508 } else if (element == deleted_element()) {
509 // This entry was deleted, so overwrite it and register that we
510 // overwrote a deleted element.
511 data->Set(entry, *new_string);
512 data->DeletedElementOverwritten();
513 return new_string;
514 } else {
515 // Return the existing string as a handle.
516 return handle(String::cast(element), isolate);
517 }
518 }
519 }
520 }
521
522 template Handle<String> StringTable::LookupKey(Isolate* isolate,
523 OneByteStringKey* key);
524 template Handle<String> StringTable::LookupKey(Isolate* isolate,
525 TwoByteStringKey* key);
526 template Handle<String> StringTable::LookupKey(Isolate* isolate,
527 SeqOneByteSubStringKey* key);
528 template Handle<String> StringTable::LookupKey(Isolate* isolate,
529 SeqTwoByteSubStringKey* key);
530
531 template Handle<String> StringTable::LookupKey(LocalIsolate* isolate,
532 OneByteStringKey* key);
533 template Handle<String> StringTable::LookupKey(LocalIsolate* isolate,
534 TwoByteStringKey* key);
535 template Handle<String> StringTable::LookupKey(LocalIsolate* isolate,
536 SeqOneByteSubStringKey* key);
537 template Handle<String> StringTable::LookupKey(LocalIsolate* isolate,
538 SeqTwoByteSubStringKey* key);
539
540 template Handle<String> StringTable::LookupKey(Isolate* isolate,
541 StringTableInsertionKey* key);
542
EnsureCapacity(IsolateRoot isolate,int additional_elements)543 StringTable::Data* StringTable::EnsureCapacity(IsolateRoot isolate,
544 int additional_elements) {
545 // This call is only allowed while the write mutex is held.
546 write_mutex_.AssertHeld();
547
548 // This load can be relaxed as the table pointer can only be modified while
549 // the lock is held.
550 Data* data = data_.load(std::memory_order_relaxed);
551
552 // Grow or shrink table if needed. We first try to shrink the table, if it
553 // is sufficiently empty; otherwise we make sure to grow it so that it has
554 // enough space.
555 int current_capacity = data->capacity();
556 int current_nof = data->number_of_elements();
557 int capacity_after_shrinking =
558 ComputeStringTableCapacityWithShrink(current_capacity, current_nof + 1);
559
560 int new_capacity = -1;
561 if (capacity_after_shrinking < current_capacity) {
562 DCHECK(StringTableHasSufficientCapacityToAdd(capacity_after_shrinking,
563 current_nof, 0, 1));
564 new_capacity = capacity_after_shrinking;
565 } else if (!StringTableHasSufficientCapacityToAdd(
566 current_capacity, current_nof,
567 data->number_of_deleted_elements(), 1)) {
568 new_capacity = ComputeStringTableCapacity(current_nof + 1);
569 }
570
571 if (new_capacity != -1) {
572 std::unique_ptr<Data> new_data =
573 Data::Resize(isolate, std::unique_ptr<Data>(data), new_capacity);
574 // `new_data` is the new owner of `data`.
575 DCHECK_EQ(new_data->PreviousData(), data);
576 // Release-store the new data pointer as `data_`, so that it can be
577 // acquire-loaded by other threads. This string table becomes the owner of
578 // the pointer.
579 data = new_data.release();
580 data_.store(data, std::memory_order_release);
581 }
582
583 return data;
584 }
585
586 // static
587 template <typename Char>
TryStringToIndexOrLookupExisting(Isolate * isolate,String string,String source,size_t start)588 Address StringTable::Data::TryStringToIndexOrLookupExisting(Isolate* isolate,
589 String string,
590 String source,
591 size_t start) {
592 // TODO(leszeks): This method doesn't really belong on StringTable::Data.
593 // Ideally it would be a free function in an anonymous namespace, but that
594 // causes issues around method and class visibility.
595
596 DisallowHeapAllocation no_gc;
597 uint64_t seed = HashSeed(isolate);
598
599 int length = string.length();
600
601 std::unique_ptr<Char[]> buffer;
602 const Char* chars;
603
604 if (source.IsConsString()) {
605 DCHECK(!source.IsFlat());
606 buffer.reset(new Char[length]);
607 String::WriteToFlat(source, buffer.get(), 0, length);
608 chars = buffer.get();
609 } else {
610 chars = source.GetChars<Char>(no_gc) + start;
611 }
612 // TODO(verwaest): Internalize to one-byte when possible.
613 SequentialStringKey<Char> key(Vector<const Char>(chars, length), seed);
614
615 // String could be an array index.
616 uint32_t hash_field = key.hash_field();
617
618 if (Name::ContainsCachedArrayIndex(hash_field)) {
619 return Smi::FromInt(String::ArrayIndexValueBits::decode(hash_field)).ptr();
620 }
621
622 if ((hash_field & Name::kIsNotIntegerIndexMask) == 0) {
623 // It is an index, but it's not cached.
624 return Smi::FromInt(ResultSentinel::kUnsupported).ptr();
625 }
626
627 Data* string_table_data =
628 isolate->string_table()->data_.load(std::memory_order_acquire);
629
630 InternalIndex entry = string_table_data->FindEntry(isolate, &key, key.hash());
631 if (entry.is_not_found()) {
632 // A string that's not an array index, and not in the string table,
633 // cannot have been used as a property name before.
634 return Smi::FromInt(ResultSentinel::kNotFound).ptr();
635 }
636
637 String internalized = String::cast(string_table_data->Get(isolate, entry));
638 if (FLAG_thin_strings) {
639 string.MakeThin(isolate, internalized);
640 }
641 return internalized.ptr();
642 }
643
644 // static
TryStringToIndexOrLookupExisting(Isolate * isolate,Address raw_string)645 Address StringTable::TryStringToIndexOrLookupExisting(Isolate* isolate,
646 Address raw_string) {
647 String string = String::cast(Object(raw_string));
648 DCHECK(!string.IsInternalizedString());
649
650 // Valid array indices are >= 0, so they cannot be mixed up with any of
651 // the result sentinels, which are negative.
652 STATIC_ASSERT(
653 !String::ArrayIndexValueBits::is_valid(ResultSentinel::kUnsupported));
654 STATIC_ASSERT(
655 !String::ArrayIndexValueBits::is_valid(ResultSentinel::kNotFound));
656
657 size_t start = 0;
658 String source = string;
659 if (source.IsSlicedString()) {
660 SlicedString sliced = SlicedString::cast(source);
661 start = sliced.offset();
662 source = sliced.parent();
663 } else if (source.IsConsString() && source.IsFlat()) {
664 source = ConsString::cast(source).first();
665 }
666 if (source.IsThinString()) {
667 source = ThinString::cast(source).actual();
668 if (string.length() == source.length()) {
669 return source.ptr();
670 }
671 }
672
673 if (source.IsOneByteRepresentation()) {
674 return StringTable::Data::TryStringToIndexOrLookupExisting<uint8_t>(
675 isolate, string, source, start);
676 }
677 return StringTable::Data::TryStringToIndexOrLookupExisting<uint16_t>(
678 isolate, string, source, start);
679 }
680
Print(IsolateRoot isolate) const681 void StringTable::Print(IsolateRoot isolate) const {
682 data_.load(std::memory_order_acquire)->Print(isolate);
683 }
684
GetCurrentMemoryUsage() const685 size_t StringTable::GetCurrentMemoryUsage() const {
686 return sizeof(*this) +
687 data_.load(std::memory_order_acquire)->GetCurrentMemoryUsage();
688 }
689
IterateElements(RootVisitor * visitor)690 void StringTable::IterateElements(RootVisitor* visitor) {
691 // This should only happen during garbage collection when background threads
692 // are paused, so the load can be relaxed.
693 DCHECK_IMPLIES(FLAG_local_heaps, isolate_->heap()->safepoint()->IsActive());
694 data_.load(std::memory_order_relaxed)->IterateElements(visitor);
695 }
696
DropOldData()697 void StringTable::DropOldData() {
698 // This should only happen during garbage collection when background threads
699 // are paused, so the load can be relaxed.
700 DCHECK_IMPLIES(FLAG_local_heaps, isolate_->heap()->safepoint()->IsActive());
701 DCHECK_NE(isolate_->heap()->gc_state(), Heap::NOT_IN_GC);
702 data_.load(std::memory_order_relaxed)->DropPreviousData();
703 }
704
NotifyElementsRemoved(int count)705 void StringTable::NotifyElementsRemoved(int count) {
706 // This should only happen during garbage collection when background threads
707 // are paused, so the load can be relaxed.
708 DCHECK_IMPLIES(FLAG_local_heaps, isolate_->heap()->safepoint()->IsActive());
709 DCHECK_NE(isolate_->heap()->gc_state(), Heap::NOT_IN_GC);
710 data_.load(std::memory_order_relaxed)->ElementsRemoved(count);
711 }
712
713 } // namespace internal
714 } // namespace v8
715