| // Copyright 2020 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. |
| |
| #include "src/base/logging.h" |
| #include "src/codegen/code-stub-assembler.h" |
| #include "src/common/globals.h" |
| #include "src/objects/descriptor-array.h" |
| #include "src/objects/property-details.h" |
| #include "src/objects/string-inl.h" |
| #include "src/objects/transitions-inl.h" |
| #include "test/cctest/cctest.h" |
| #include "test/cctest/compiler/code-assembler-tester.h" |
| #include "test/cctest/compiler/function-tester.h" |
| #include "test/cctest/test-transitions.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| namespace { |
| |
| using Label = compiler::CodeAssemblerLabel; |
| template <class T> |
| using TVariable = compiler::TypedCodeAssemblerVariable<T>; |
| |
| Handle<Name> NewNameWithHash(Isolate* isolate, const char* str, uint32_t hash, |
| bool is_integer) { |
| uint32_t hash_field = hash << Name::kHashShift; |
| |
| static_assert(Name::kNofHashBitFields == 2, "This test needs updating"); |
| static_assert(Name::kHashNotComputedMask == 1, "This test needs updating"); |
| static_assert(Name::kIsNotIntegerIndexMask == 2, "This test needs updating"); |
| |
| if (!is_integer) { |
| hash_field |= Name::kIsNotIntegerIndexMask; |
| } |
| Handle<Name> name = isolate->factory()->NewOneByteInternalizedString( |
| OneByteVector(str), hash_field); |
| name->set_hash_field(hash_field); |
| CHECK(name->IsUniqueName()); |
| return name; |
| } |
| |
| template <typename... Args> |
| MaybeHandle<Object> Call(Isolate* isolate, Handle<JSFunction> function, |
| Args... args) { |
| const int nof_args = sizeof...(Args); |
| Handle<Object> call_args[] = {args...}; |
| Handle<Object> receiver = isolate->factory()->undefined_value(); |
| return Execution::Call(isolate, function, receiver, nof_args, call_args); |
| } |
| |
| void CheckDescriptorArrayLookups(Isolate* isolate, Handle<Map> map, |
| std::vector<Handle<Name>>& names, |
| Handle<JSFunction> csa_lookup) { |
| // Test C++ implementation. |
| { |
| DisallowHeapAllocation no_gc; |
| DescriptorArray descriptors = map->instance_descriptors(kRelaxedLoad); |
| DCHECK(descriptors.IsSortedNoDuplicates()); |
| int nof_descriptors = descriptors.number_of_descriptors(); |
| |
| for (size_t i = 0; i < names.size(); ++i) { |
| Name name = *names[i]; |
| InternalIndex index = descriptors.Search(name, nof_descriptors, false); |
| CHECK(index.is_found()); |
| CHECK_EQ(i, index.as_uint32()); |
| } |
| } |
| |
| // Test CSA implementation. |
| if (!FLAG_jitless) { |
| for (size_t i = 0; i < names.size(); ++i) { |
| Handle<Object> name_index = |
| Call(isolate, csa_lookup, map, names[i]).ToHandleChecked(); |
| CHECK(name_index->IsSmi()); |
| CHECK_EQ(DescriptorArray::ToKeyIndex(static_cast<int>(i)), |
| Smi::ToInt(*name_index)); |
| } |
| } |
| } |
| |
| void CheckTransitionArrayLookups(Isolate* isolate, |
| Handle<TransitionArray> transitions, |
| std::vector<Handle<Map>>& maps, |
| Handle<JSFunction> csa_lookup) { |
| // Test C++ implementation. |
| { |
| DisallowHeapAllocation no_gc; |
| DCHECK(transitions->IsSortedNoDuplicates()); |
| |
| for (size_t i = 0; i < maps.size(); ++i) { |
| Map expected_map = *maps[i]; |
| Name name = expected_map.instance_descriptors(kRelaxedLoad) |
| .GetKey(expected_map.LastAdded()); |
| |
| Map map = transitions->SearchAndGetTargetForTesting(PropertyKind::kData, |
| name, NONE); |
| CHECK(!map.is_null()); |
| CHECK_EQ(expected_map, map); |
| } |
| } |
| |
| // Test CSA implementation. |
| if (!FLAG_jitless) { |
| for (size_t i = 0; i < maps.size(); ++i) { |
| Handle<Map> expected_map = maps[i]; |
| Handle<Name> name(expected_map->instance_descriptors(kRelaxedLoad) |
| .GetKey(expected_map->LastAdded()), |
| isolate); |
| |
| Handle<Object> transition_map = |
| Call(isolate, csa_lookup, transitions, name).ToHandleChecked(); |
| CHECK(transition_map->IsMap()); |
| CHECK_EQ(*expected_map, *transition_map); |
| } |
| } |
| } |
| |
| // Creates function with (Map, Name) arguments. Returns Smi with the index of |
| // the name value of the found descriptor (DescriptorArray::ToKeyIndex()) |
| // or null otherwise. |
| Handle<JSFunction> CreateCsaDescriptorArrayLookup(Isolate* isolate) { |
| // We are not allowed to generate code in jitless mode. |
| if (FLAG_jitless) return Handle<JSFunction>(); |
| |
| // Preallocate handle for the result in the current handle scope. |
| Handle<JSFunction> result_function(JSFunction{}, isolate); |
| |
| const int kNumParams = 2; |
| |
| compiler::CodeAssemblerTester asm_tester( |
| isolate, kNumParams + 1, // +1 to include receiver. |
| CodeKind::FOR_TESTING); |
| { |
| CodeStubAssembler m(asm_tester.state()); |
| |
| auto map = m.Parameter<Map>(1); |
| auto unique_name = m.Parameter<Name>(2); |
| |
| Label passed(&m), failed(&m); |
| Label if_found(&m), if_not_found(&m); |
| TVariable<IntPtrT> var_name_index(&m); |
| |
| TNode<Uint32T> bit_field3 = m.LoadMapBitField3(map); |
| TNode<DescriptorArray> descriptors = m.LoadMapDescriptors(map); |
| |
| m.DescriptorLookup(unique_name, descriptors, bit_field3, &if_found, |
| &var_name_index, &if_not_found); |
| |
| m.BIND(&if_found); |
| m.Return(m.SmiTag(var_name_index.value())); |
| |
| m.BIND(&if_not_found); |
| m.Return(m.NullConstant()); |
| } |
| |
| { |
| compiler::FunctionTester ft(asm_tester.GenerateCode(), kNumParams); |
| // Copy function value to a handle created in the outer handle scope. |
| result_function.PatchValue(*ft.function); |
| } |
| |
| return result_function; |
| } |
| |
| // Creates function with (TransitionArray, Name) arguments. Returns transition |
| // map if transition is found or null otherwise. |
| Handle<JSFunction> CreateCsaTransitionArrayLookup(Isolate* isolate) { |
| // We are not allowed to generate code in jitless mode. |
| if (FLAG_jitless) return Handle<JSFunction>(); |
| |
| // Preallocate handle for the result in the current handle scope. |
| Handle<JSFunction> result_function(JSFunction{}, isolate); |
| |
| const int kNumParams = 2; |
| compiler::CodeAssemblerTester asm_tester( |
| isolate, kNumParams + 1, // +1 to include receiver. |
| CodeKind::FOR_TESTING); |
| { |
| CodeStubAssembler m(asm_tester.state()); |
| |
| auto transitions = m.Parameter<TransitionArray>(1); |
| auto unique_name = m.Parameter<Name>(2); |
| |
| Label passed(&m), failed(&m); |
| Label if_found(&m), if_not_found(&m); |
| TVariable<IntPtrT> var_name_index(&m); |
| |
| m.TransitionLookup(unique_name, transitions, &if_found, &var_name_index, |
| &if_not_found); |
| |
| m.BIND(&if_found); |
| { |
| STATIC_ASSERT(kData == 0); |
| STATIC_ASSERT(NONE == 0); |
| const int kKeyToTargetOffset = (TransitionArray::kEntryTargetIndex - |
| TransitionArray::kEntryKeyIndex) * |
| kTaggedSize; |
| TNode<Map> transition_map = m.CAST(m.GetHeapObjectAssumeWeak( |
| m.LoadArrayElement(transitions, WeakFixedArray::kHeaderSize, |
| var_name_index.value(), kKeyToTargetOffset))); |
| m.Return(transition_map); |
| } |
| |
| m.BIND(&if_not_found); |
| m.Return(m.NullConstant()); |
| } |
| |
| { |
| compiler::FunctionTester ft(asm_tester.GenerateCode(), kNumParams); |
| // Copy function value to a handle created in the outer handle scope. |
| result_function.PatchValue(*ft.function); |
| } |
| |
| return result_function; |
| } |
| |
| } // namespace |
| |
| TEST(DescriptorArrayHashCollisionMassive) { |
| CcTest::InitializeVM(); |
| Isolate* isolate = CcTest::i_isolate(); |
| HandleScope handle_scope(isolate); |
| |
| static_assert(Name::kNofHashBitFields == 2, "This test needs updating"); |
| |
| std::vector<Handle<Name>> names; |
| |
| // Use the same hash value for all names. |
| uint32_t hash = |
| static_cast<uint32_t>(isolate->GenerateIdentityHash(Name::kHashBitMask)); |
| |
| for (int i = 0; i < kMaxNumberOfDescriptors / 2; ++i) { |
| // Add pairs of names having the same base hash value but having different |
| // values of is_integer bit. |
| bool first_is_integer = (i & 1) != 0; |
| bool second_is_integer = (i & 2) != 0; |
| |
| names.push_back(NewNameWithHash(isolate, "a", hash, first_is_integer)); |
| names.push_back(NewNameWithHash(isolate, "b", hash, second_is_integer)); |
| } |
| |
| // Create descriptor array with the created names by appending fields to some |
| // map. DescriptorArray marking relies on the fact that it's attached to an |
| // owning map. |
| Handle<Map> map = Map::Create(isolate, 0); |
| |
| Handle<FieldType> any_type = FieldType::Any(isolate); |
| |
| for (size_t i = 0; i < names.size(); ++i) { |
| map = Map::CopyWithField(isolate, map, names[i], any_type, NONE, |
| PropertyConstness::kMutable, |
| Representation::Tagged(), OMIT_TRANSITION) |
| .ToHandleChecked(); |
| } |
| |
| Handle<JSFunction> csa_lookup = CreateCsaDescriptorArrayLookup(isolate); |
| |
| CheckDescriptorArrayLookups(isolate, map, names, csa_lookup); |
| |
| // Sort descriptor array and check it again. |
| map->instance_descriptors(kRelaxedLoad).Sort(); |
| CheckDescriptorArrayLookups(isolate, map, names, csa_lookup); |
| } |
| |
| TEST(DescriptorArrayHashCollision) { |
| CcTest::InitializeVM(); |
| Isolate* isolate = CcTest::i_isolate(); |
| HandleScope handle_scope(isolate); |
| |
| static_assert(Name::kNofHashBitFields == 2, "This test needs updating"); |
| |
| std::vector<Handle<Name>> names; |
| uint32_t hash = 0; |
| |
| for (int i = 0; i < kMaxNumberOfDescriptors / 2; ++i) { |
| if (i % 2 == 0) { |
| // Change hash value for every pair of names. |
| hash = static_cast<uint32_t>( |
| isolate->GenerateIdentityHash(Name::kHashBitMask)); |
| } |
| |
| // Add pairs of names having the same base hash value but having different |
| // values of is_integer bit. |
| bool first_is_integer = (i & 1) != 0; |
| bool second_is_integer = (i & 2) != 0; |
| |
| names.push_back(NewNameWithHash(isolate, "a", hash, first_is_integer)); |
| names.push_back(NewNameWithHash(isolate, "b", hash, second_is_integer)); |
| } |
| |
| // Create descriptor array with the created names by appending fields to some |
| // map. DescriptorArray marking relies on the fact that it's attached to an |
| // owning map. |
| Handle<Map> map = Map::Create(isolate, 0); |
| |
| Handle<FieldType> any_type = FieldType::Any(isolate); |
| |
| for (size_t i = 0; i < names.size(); ++i) { |
| map = Map::CopyWithField(isolate, map, names[i], any_type, NONE, |
| PropertyConstness::kMutable, |
| Representation::Tagged(), OMIT_TRANSITION) |
| .ToHandleChecked(); |
| } |
| |
| Handle<JSFunction> csa_lookup = CreateCsaDescriptorArrayLookup(isolate); |
| |
| CheckDescriptorArrayLookups(isolate, map, names, csa_lookup); |
| |
| // Sort descriptor array and check it again. |
| map->instance_descriptors(kRelaxedLoad).Sort(); |
| CheckDescriptorArrayLookups(isolate, map, names, csa_lookup); |
| } |
| |
| TEST(TransitionArrayHashCollisionMassive) { |
| CcTest::InitializeVM(); |
| Isolate* isolate = CcTest::i_isolate(); |
| HandleScope handle_scope(isolate); |
| |
| static_assert(Name::kNofHashBitFields == 2, "This test needs updating"); |
| |
| std::vector<Handle<Name>> names; |
| |
| // Use the same hash value for all names. |
| uint32_t hash = |
| static_cast<uint32_t>(isolate->GenerateIdentityHash(Name::kHashBitMask)); |
| |
| for (int i = 0; i < TransitionsAccessor::kMaxNumberOfTransitions / 2; ++i) { |
| // Add pairs of names having the same base hash value but having different |
| // values of is_integer bit. |
| bool first_is_integer = (i & 1) != 0; |
| bool second_is_integer = (i & 2) != 0; |
| |
| names.push_back(NewNameWithHash(isolate, "a", hash, first_is_integer)); |
| names.push_back(NewNameWithHash(isolate, "b", hash, second_is_integer)); |
| } |
| |
| // Create transitions for each name. |
| Handle<Map> root_map = Map::Create(isolate, 0); |
| |
| std::vector<Handle<Map>> maps; |
| |
| Handle<FieldType> any_type = FieldType::Any(isolate); |
| |
| for (size_t i = 0; i < names.size(); ++i) { |
| Handle<Map> map = |
| Map::CopyWithField(isolate, root_map, names[i], any_type, NONE, |
| PropertyConstness::kMutable, |
| Representation::Tagged(), INSERT_TRANSITION) |
| .ToHandleChecked(); |
| maps.push_back(map); |
| } |
| |
| Handle<JSFunction> csa_lookup = CreateCsaTransitionArrayLookup(isolate); |
| |
| Handle<TransitionArray> transition_array( |
| TestTransitionsAccessor(isolate, root_map).transitions(), isolate); |
| |
| CheckTransitionArrayLookups(isolate, transition_array, maps, csa_lookup); |
| |
| // Sort transition array and check it again. |
| transition_array->Sort(); |
| CheckTransitionArrayLookups(isolate, transition_array, maps, csa_lookup); |
| } |
| |
| TEST(TransitionArrayHashCollision) { |
| CcTest::InitializeVM(); |
| Isolate* isolate = CcTest::i_isolate(); |
| HandleScope handle_scope(isolate); |
| |
| static_assert(Name::kNofHashBitFields == 2, "This test needs updating"); |
| |
| std::vector<Handle<Name>> names; |
| |
| // Use the same hash value for all names. |
| uint32_t hash = |
| static_cast<uint32_t>(isolate->GenerateIdentityHash(Name::kHashBitMask)); |
| |
| for (int i = 0; i < TransitionsAccessor::kMaxNumberOfTransitions / 2; ++i) { |
| if (i % 2 == 0) { |
| // Change hash value for every pair of names. |
| hash = static_cast<uint32_t>( |
| isolate->GenerateIdentityHash(Name::kHashBitMask)); |
| } |
| // Add pairs of names having the same base hash value but having different |
| // values of is_integer bit. |
| bool first_is_integer = (i & 1) != 0; |
| bool second_is_integer = (i & 2) != 0; |
| |
| names.push_back(NewNameWithHash(isolate, "a", hash, first_is_integer)); |
| names.push_back(NewNameWithHash(isolate, "b", hash, second_is_integer)); |
| } |
| |
| // Create transitions for each name. |
| Handle<Map> root_map = Map::Create(isolate, 0); |
| |
| std::vector<Handle<Map>> maps; |
| |
| Handle<FieldType> any_type = FieldType::Any(isolate); |
| |
| for (size_t i = 0; i < names.size(); ++i) { |
| Handle<Map> map = |
| Map::CopyWithField(isolate, root_map, names[i], any_type, NONE, |
| PropertyConstness::kMutable, |
| Representation::Tagged(), INSERT_TRANSITION) |
| .ToHandleChecked(); |
| maps.push_back(map); |
| } |
| |
| Handle<JSFunction> csa_lookup = CreateCsaTransitionArrayLookup(isolate); |
| |
| Handle<TransitionArray> transition_array( |
| TestTransitionsAccessor(isolate, root_map).transitions(), isolate); |
| |
| CheckTransitionArrayLookups(isolate, transition_array, maps, csa_lookup); |
| |
| // Sort transition array and check it again. |
| transition_array->Sort(); |
| CheckTransitionArrayLookups(isolate, transition_array, maps, csa_lookup); |
| } |
| |
| } // namespace internal |
| } // namespace v8 |
