FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

deps: V8: cherry-pick 00f6e834029f · nodejs/node@3839c4a · GitHub

/ node Public

Commit 3839c4a

Browse files
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

5 files changed

Lines changed: 120 additions & 6 deletions

File tree

‎common.gypi‎

Lines 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

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

Lines 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());

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

Lines 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++) {

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

Lines 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

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

Lines 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)
Back | FazBrowse Home | New Git URL