Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 3839c4a

Browse filesBrowse files
joyeecheungRafaelGSS
joyeecheung
authored and
RafaelGSS
committed
deps: V8: cherry-pick 00f6e834029f
Original commit message: [runtime] always sort transition arrays during rehashing After rehashing, the arrays are no longer in hash-sorted order. In this case, we need to force a re-sort even for small arrays, so that subsequent linear searches can find the correct transition and avoid inserting duplicates. Refs: #61898 (comment) Change-Id: Ia813d1fb9d23e08012811d672052d235c0e0bf4d Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7723678 Commit-Queue: Joyee Cheung <joyee@igalia.com> Reviewed-by: Igor Sheludko <ishell@chromium.org> Cr-Commit-Position: refs/heads/main@{#106255} Refs: v8/v8@00f6e83 PR-URL: #61898 Reviewed-By: Antoine du Hamel <duhamelantoine1995@gmail.com> Reviewed-By: Filip Skokan <panva.ip@gmail.com> Reviewed-By: Rafael Gonzaga <rafael.nunu@hotmail.com> Reviewed-By: Chengzhong Wu <legendecas@gmail.com> (cherry picked from commit 2387042)
1 parent 44f64f1 commit 3839c4a
Copy full SHA for 3839c4a

5 files changed

+120-6Lines changed: 120 additions & 6 deletions

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎common.gypi‎

Copy file name to clipboardExpand all lines: common.gypi
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,7 @@
3838

3939
# Reset this number to 0 on major V8 upgrades.
4040
# Increment by one for each non-official patch applied to deps/v8.
41-
'v8_embedder_string': '-node.13',
41+
'v8_embedder_string': '-node.14',
4242

4343
##### V8 defaults for Node.js #####
4444

Collapse file

‎deps/v8/src/objects/objects.cc‎

Copy file name to clipboardExpand all lines: deps/v8/src/objects/objects.cc
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2281,7 +2281,7 @@ void HeapObject::RehashBasedOnMap(IsolateT* isolate) {
22812281
Cast<DescriptorArray>(*this)->Sort();
22822282
break;
22832283
case TRANSITION_ARRAY_TYPE:
2284-
Cast<TransitionArray>(*this)->Sort();
2284+
Cast<TransitionArray>(*this)->Sort(true);
22852285
break;
22862286
case SMALL_ORDERED_HASH_MAP_TYPE:
22872287
DCHECK_EQ(0, Cast<SmallOrderedHashMap>(*this)->NumberOfElements());
Collapse file

‎deps/v8/src/objects/transitions.cc‎

Copy file name to clipboardExpand all lines: deps/v8/src/objects/transitions.cc
+6-3Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -789,12 +789,15 @@ void TransitionArray::ForEachTransitionTo(
789789
}
790790
}
791791

792-
void TransitionArray::Sort() {
792+
void TransitionArray::Sort(bool force) {
793793
DisallowGarbageCollection no_gc;
794794
// In-place insertion sort.
795795
int length = number_of_transitions();
796-
// Sorting matters only for binary search.
797-
if (length <= kMaxElementsForLinearSearch) return;
796+
// After rehashing, the arrays are no longer in hash-sorted order.
797+
// In this case, we need to force a re-sort even for small arrays,
798+
// so that subsequent linear searches can find the correct transition
799+
// and avoid inserting duplicates.
800+
if (!force && length <= kMaxElementsForLinearSearch) return;
798801

799802
ReadOnlyRoots roots = GetReadOnlyRoots();
800803
for (int i = 1; i < length; i++) {
Collapse file

‎deps/v8/src/objects/transitions.h‎

Copy file name to clipboardExpand all lines: deps/v8/src/objects/transitions.h
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -341,7 +341,7 @@ class TransitionArray : public WeakFixedArray {
341341
V8_EXPORT_PRIVATE bool IsSortedNoDuplicates();
342342
#endif
343343

344-
V8_EXPORT_PRIVATE void Sort();
344+
V8_EXPORT_PRIVATE void Sort(bool force = false);
345345

346346
void PrintInternal(std::ostream& os);
347347

Collapse file

‎deps/v8/test/cctest/test-transitions.cc‎

Copy file name to clipboardExpand all lines: deps/v8/test/cctest/test-transitions.cc
+111Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -464,5 +464,116 @@ UNINITIALIZED_TEST(TransitionArray_InsertToBinarySearchSizeAfterRehashing) {
464464
FreeCurrentEmbeddedBlob();
465465
}
466466

467+
UNINITIALIZED_TEST(TransitionArray_RehashNoDuplicatesWithinLinearSearchSize) {
468+
v8_flags.rehash_snapshot = true;
469+
v8_flags.hash_seed = 42;
470+
v8_flags.allow_natives_syntax = true;
471+
DisableEmbeddedBlobRefcounting();
472+
v8::StartupData blob;
473+
// Stay within linear search size.
474+
constexpr int initial_size = TransitionArray::kMaxElementsForLinearSearch / 2;
475+
476+
{
477+
v8::Isolate::CreateParams testing_params;
478+
testing_params.array_buffer_allocator = CcTest::array_buffer_allocator();
479+
v8::SnapshotCreator creator(testing_params);
480+
v8::Isolate* isolate = creator.GetIsolate();
481+
{
482+
v8::HandleScope handle_scope(isolate);
483+
v8::Local<v8::Context> context = v8::Context::New(isolate);
484+
v8::Context::Scope context_scope(context);
485+
Isolate* i_isolate = reinterpret_cast<Isolate*>(isolate);
486+
v8::Local<v8::Object> obj = v8::Object::New(isolate);
487+
DirectHandle<Map> first_map =
488+
direct_handle(v8::Utils::OpenDirectHandle(*obj)->map(), i_isolate);
489+
490+
{
491+
TestTransitionsAccessor transitions(i_isolate, first_map);
492+
CHECK_EQ(0, transitions.NumberOfTransitions());
493+
}
494+
495+
// Insert transitions that will be rehashed on deserialization.
496+
v8::Local<v8::Value> null_value = v8::Null(isolate);
497+
v8::LocalVector<v8::Value> objects(isolate);
498+
for (int i = 0; i < initial_size; i++) {
499+
std::string prop_name = "prop_" + std::to_string(i);
500+
v8::Local<v8::String> name =
501+
v8::String::NewFromUtf8(isolate, prop_name.c_str(),
502+
v8::NewStringType::kNormal)
503+
.ToLocalChecked();
504+
v8::Local<v8::Object> new_obj = v8::Object::New(isolate);
505+
new_obj->Set(context, name, null_value).Check();
506+
objects.push_back(new_obj);
507+
}
508+
context->Global()
509+
->Set(context, v8_str("objects_for_transitions"),
510+
v8::Array::New(isolate, objects.data(), objects.size()))
511+
.Check();
512+
513+
creator.SetDefaultContext(context);
514+
515+
TestTransitionsAccessor transitions(i_isolate, first_map);
516+
CHECK_EQ(initial_size, transitions.NumberOfTransitions());
517+
}
518+
blob =
519+
creator.CreateBlob(v8::SnapshotCreator::FunctionCodeHandling::kClear);
520+
CHECK(blob.CanBeRehashed());
521+
}
522+
523+
// Deserialize with a different hash seed to trigger rehashing.
524+
v8_flags.hash_seed = 1337;
525+
v8::Isolate::CreateParams testing_params;
526+
testing_params.array_buffer_allocator = CcTest::array_buffer_allocator();
527+
testing_params.snapshot_blob = &blob;
528+
v8::Isolate* isolate = v8::Isolate::New(testing_params);
529+
{
530+
v8::Isolate::Scope isolate_scope(isolate);
531+
CHECK_EQ(static_cast<uint64_t>(1337),
532+
HashSeed(reinterpret_cast<Isolate*>(isolate)).seed());
533+
v8::HandleScope handle_scope(isolate);
534+
v8::Local<v8::Context> context = v8::Context::New(isolate);
535+
CHECK(!context.IsEmpty());
536+
v8::Context::Scope context_scope(context);
537+
538+
Isolate* i_isolate = reinterpret_cast<Isolate*>(isolate);
539+
v8::Local<v8::Object> obj = v8::Object::New(isolate);
540+
DirectHandle<Map> first_map =
541+
direct_handle(v8::Utils::OpenDirectHandle(*obj)->map(), i_isolate);
542+
543+
// Collect existing transition keys from the rehashed array.
544+
Handle<String> keys[initial_size];
545+
{
546+
TestTransitionsAccessor transitions(i_isolate, first_map);
547+
CHECK_EQ(initial_size, transitions.NumberOfTransitions());
548+
for (int i = 0; i < initial_size; i++) {
549+
keys[i] = handle(Cast<String>(transitions.GetKey(i)), i_isolate);
550+
}
551+
}
552+
553+
// For each existing transition, create a fresh map and re-insert it with
554+
// the same field name.
555+
for (int i = 0; i < initial_size; i++) {
556+
Handle<Map> new_map =
557+
Map::CopyWithField(i_isolate, first_map, keys[i],
558+
FieldType::Any(i_isolate), NONE,
559+
PropertyConstness::kMutable,
560+
Representation::Tagged(), OMIT_TRANSITION)
561+
.ToHandleChecked();
562+
TransitionsAccessor::Insert(i_isolate, first_map, keys[i], new_map,
563+
PROPERTY_TRANSITION);
564+
}
565+
566+
// Verify no duplicates were created.
567+
{
568+
TestTransitionsAccessor transitions(i_isolate, first_map);
569+
CHECK_EQ(initial_size, transitions.NumberOfTransitions());
570+
}
571+
}
572+
573+
isolate->Dispose();
574+
delete[] blob.data;
575+
FreeCurrentEmbeddedBlob();
576+
}
577+
467578
} // namespace internal
468579
} // namespace v8

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.