Welcome to mirror list, hosted at ThFree Co, Russian Federation.

github.com/nodejs/node.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/deps
diff options
context:
space:
mode:
authorMichaël Zasso <targos@protonmail.com>2021-04-17 18:34:15 +0300
committerMichaël Zasso <targos@protonmail.com>2021-04-30 13:54:14 +0300
commitc5fe3a226a6d843bd3f5569dd1b6312f183e7d54 (patch)
tree2db4216828aab5d465aeda7b8cf0ab4f6abb66c1 /deps
parent7dd68ac5b6f9a10bfd12913118f750a6d73a978a (diff)
deps: V8: cherry-pick 1a7d55a9a427
Original commit message: Merged: [runtime] Fix sorted order of DescriptorArray entries Revision: 518d67ad652fc24b7eb03e48bb342f952d4ccf74 This is a reland of the previous merge which addresses the cctest link failure in component build mode. BUG=chromium:1133527 NOTRY=true NOPRESUBMIT=true NOTREECHECKS=true R=verwaest@chromium.org Change-Id: Icbbc69fd5403fd0c2ab6d07d4340292b2b8c72b9 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2504264 Reviewed-by: Toon Verwaest <verwaest@chromium.org> Cr-Commit-Position: refs/branch-heads/8.6@{#40} Cr-Branched-From: a64aed2333abf49e494d2a5ce24bbd14fff19f60-refs/heads/8.6.395@{#1} Cr-Branched-From: a626bc036236c9bf92ac7b87dc40c9e538b087e3-refs/heads/master@{#69472} Refs: https://github.com/v8/v8/commit/1a7d55a9a4274897e1e2e744b99800c3a491af7f PR-URL: https://github.com/nodejs/node/pull/38275 Reviewed-By: Matteo Collina <matteo.collina@gmail.com> Reviewed-By: Jiawen Geng <technicalcute@gmail.com> Reviewed-By: Shelley Vohr <codebytere@gmail.com>
Diffstat (limited to 'deps')
-rw-r--r--deps/v8/src/codegen/code-stub-assembler.cc19
-rw-r--r--deps/v8/src/codegen/code-stub-assembler.h7
-rw-r--r--deps/v8/src/diagnostics/objects-debug.cc6
-rw-r--r--deps/v8/src/objects/descriptor-array-inl.h2
-rw-r--r--deps/v8/src/objects/descriptor-array.h2
-rw-r--r--deps/v8/src/objects/fixed-array-inl.h10
-rw-r--r--deps/v8/src/objects/name-inl.h6
-rw-r--r--deps/v8/src/objects/name.h8
-rw-r--r--deps/v8/src/objects/objects.cc14
-rw-r--r--deps/v8/src/objects/transitions-inl.h8
-rw-r--r--deps/v8/src/objects/transitions.cc4
-rw-r--r--deps/v8/src/objects/transitions.h13
-rw-r--r--deps/v8/test/cctest/BUILD.gn1
-rw-r--r--deps/v8/test/cctest/test-descriptor-array.cc424
-rw-r--r--deps/v8/test/cctest/test-transitions.h2
15 files changed, 489 insertions, 37 deletions
diff --git a/deps/v8/src/codegen/code-stub-assembler.cc b/deps/v8/src/codegen/code-stub-assembler.cc
index 901ce0c7b49..50fb563244c 100644
--- a/deps/v8/src/codegen/code-stub-assembler.cc
+++ b/deps/v8/src/codegen/code-stub-assembler.cc
@@ -1801,12 +1801,13 @@ TNode<IntPtrT> CodeStubAssembler::LoadJSReceiverIdentityHash(
return var_hash.value();
}
-TNode<Uint32T> CodeStubAssembler::LoadNameHashField(SloppyTNode<Name> name) {
- CSA_ASSERT(this, IsName(name));
- return LoadObjectField<Uint32T>(name, Name::kHashFieldOffset);
+TNode<Uint32T> CodeStubAssembler::LoadNameHashAssumeComputed(TNode<Name> name) {
+ TNode<Uint32T> hash_field = LoadNameHashField(name);
+ CSA_ASSERT(this, IsClearWord32(hash_field, Name::kHashNotComputedMask));
+ return Unsigned(Word32Shr(hash_field, Int32Constant(Name::kHashShift)));
}
-TNode<Uint32T> CodeStubAssembler::LoadNameHash(SloppyTNode<Name> name,
+TNode<Uint32T> CodeStubAssembler::LoadNameHash(TNode<Name> name,
Label* if_hash_not_computed) {
TNode<Uint32T> hash_field = LoadNameHashField(name);
if (if_hash_not_computed != nullptr) {
@@ -1994,13 +1995,13 @@ TNode<T> CodeStubAssembler::LoadArrayElement(TNode<Array> array,
}
}
-template TNode<MaybeObject>
+template V8_EXPORT_PRIVATE TNode<MaybeObject>
CodeStubAssembler::LoadArrayElement<TransitionArray>(TNode<TransitionArray>,
int, Node*, int,
ParameterMode,
LoadSensitivity);
-template TNode<MaybeObject>
+template V8_EXPORT_PRIVATE TNode<MaybeObject>
CodeStubAssembler::LoadArrayElement<DescriptorArray>(TNode<DescriptorArray>,
int, Node*, int,
ParameterMode,
@@ -8063,7 +8064,7 @@ void CodeStubAssembler::LookupBinary(TNode<Name> unique_name,
TNode<Uint32T> limit =
Unsigned(Int32Sub(NumberOfEntries<Array>(array), Int32Constant(1)));
TVARIABLE(Uint32T, var_high, limit);
- TNode<Uint32T> hash = LoadNameHashField(unique_name);
+ TNode<Uint32T> hash = LoadNameHashAssumeComputed(unique_name);
CSA_ASSERT(this, Word32NotEqual(hash, Int32Constant(0)));
// Assume non-empty array.
@@ -8081,7 +8082,7 @@ void CodeStubAssembler::LookupBinary(TNode<Name> unique_name,
TNode<Uint32T> sorted_key_index = GetSortedKeyIndex<Array>(array, mid);
TNode<Name> mid_name = GetKey<Array>(array, sorted_key_index);
- TNode<Uint32T> mid_hash = LoadNameHashField(mid_name);
+ TNode<Uint32T> mid_hash = LoadNameHashAssumeComputed(mid_name);
Label mid_greater(this), mid_less(this), merge(this);
Branch(Uint32GreaterThanOrEqual(mid_hash, hash), &mid_greater, &mid_less);
@@ -8108,7 +8109,7 @@ void CodeStubAssembler::LookupBinary(TNode<Name> unique_name,
TNode<Uint32T> sort_index =
GetSortedKeyIndex<Array>(array, var_low.value());
TNode<Name> current_name = GetKey<Array>(array, sort_index);
- TNode<Uint32T> current_hash = LoadNameHashField(current_name);
+ TNode<Uint32T> current_hash = LoadNameHashAssumeComputed(current_name);
GotoIf(Word32NotEqual(current_hash, hash), if_not_found);
Label next(this);
GotoIf(TaggedNotEqual(current_name, unique_name), &next);
diff --git a/deps/v8/src/codegen/code-stub-assembler.h b/deps/v8/src/codegen/code-stub-assembler.h
index b01729c73db..23b99377d8d 100644
--- a/deps/v8/src/codegen/code-stub-assembler.h
+++ b/deps/v8/src/codegen/code-stub-assembler.h
@@ -1353,13 +1353,12 @@ class V8_EXPORT_PRIVATE CodeStubAssembler
// Check if the map is set for slow properties.
TNode<BoolT> IsDictionaryMap(SloppyTNode<Map> map);
- // Load the hash field of a name as an uint32 value.
- TNode<Uint32T> LoadNameHashField(SloppyTNode<Name> name);
- // Load the hash value of a name as an uint32 value.
+ // Load the Name::hash() value of a name as an uint32 value.
// If {if_hash_not_computed} label is specified then it also checks if
// hash is actually computed.
- TNode<Uint32T> LoadNameHash(SloppyTNode<Name> name,
+ TNode<Uint32T> LoadNameHash(TNode<Name> name,
Label* if_hash_not_computed = nullptr);
+ TNode<Uint32T> LoadNameHashAssumeComputed(TNode<Name> name);
// Load length field of a String object as Smi value.
TNode<Smi> LoadStringLengthAsSmi(TNode<String> string);
diff --git a/deps/v8/src/diagnostics/objects-debug.cc b/deps/v8/src/diagnostics/objects-debug.cc
index 698b92c6162..4925a09a004 100644
--- a/deps/v8/src/diagnostics/objects-debug.cc
+++ b/deps/v8/src/diagnostics/objects-debug.cc
@@ -1667,12 +1667,13 @@ bool DescriptorArray::IsSortedNoDuplicates(int valid_entries) {
uint32_t current = 0;
for (int i = 0; i < number_of_descriptors(); i++) {
Name key = GetSortedKey(i);
+ CHECK(key.HasHashCode());
if (key == current_key) {
Print();
return false;
}
current_key = key;
- uint32_t hash = GetSortedKey(i).Hash();
+ uint32_t hash = key.hash();
if (hash < current) {
Print();
return false;
@@ -1691,7 +1692,8 @@ bool TransitionArray::IsSortedNoDuplicates(int valid_entries) {
for (int i = 0; i < number_of_transitions(); i++) {
Name key = GetSortedKey(i);
- uint32_t hash = key.Hash();
+ CHECK(key.HasHashCode());
+ uint32_t hash = key.hash();
PropertyKind kind = kData;
PropertyAttributes attributes = NONE;
if (!TransitionsAccessor::IsSpecialTransition(key.GetReadOnlyRoots(),
diff --git a/deps/v8/src/objects/descriptor-array-inl.h b/deps/v8/src/objects/descriptor-array-inl.h
index 357a6732e22..74f984d6bd2 100644
--- a/deps/v8/src/objects/descriptor-array-inl.h
+++ b/deps/v8/src/objects/descriptor-array-inl.h
@@ -226,7 +226,7 @@ void DescriptorArray::Append(Descriptor* desc) {
for (insertion = descriptor_number; insertion > 0; --insertion) {
Name key = GetSortedKey(insertion - 1);
- if (key.Hash() <= hash) break;
+ if (key.hash() <= hash) break;
SetSortedKey(insertion, GetSortedKeyIndex(insertion - 1));
}
diff --git a/deps/v8/src/objects/descriptor-array.h b/deps/v8/src/objects/descriptor-array.h
index 61da8dc240c..d752ca20b11 100644
--- a/deps/v8/src/objects/descriptor-array.h
+++ b/deps/v8/src/objects/descriptor-array.h
@@ -113,7 +113,7 @@ class DescriptorArray
int slack = 0);
// Sort the instance descriptors by the hash codes of their keys.
- void Sort();
+ V8_EXPORT_PRIVATE void Sort();
// Search the instance descriptors for given name.
V8_INLINE InternalIndex Search(Name name, int number_of_own_descriptors);
diff --git a/deps/v8/src/objects/fixed-array-inl.h b/deps/v8/src/objects/fixed-array-inl.h
index 25c80807066..b89486d3811 100644
--- a/deps/v8/src/objects/fixed-array-inl.h
+++ b/deps/v8/src/objects/fixed-array-inl.h
@@ -212,7 +212,7 @@ int BinarySearch(T* array, Name name, int valid_entries,
DCHECK(search_mode == ALL_ENTRIES || out_insertion_index == nullptr);
int low = 0;
int high = array->number_of_entries() - 1;
- uint32_t hash = name.hash_field();
+ uint32_t hash = name.hash();
int limit = high;
DCHECK(low <= high);
@@ -220,7 +220,7 @@ int BinarySearch(T* array, Name name, int valid_entries,
while (low != high) {
int mid = low + (high - low) / 2;
Name mid_name = array->GetSortedKey(mid);
- uint32_t mid_hash = mid_name.hash_field();
+ uint32_t mid_hash = mid_name.hash();
if (mid_hash >= hash) {
high = mid;
@@ -232,7 +232,7 @@ int BinarySearch(T* array, Name name, int valid_entries,
for (; low <= limit; ++low) {
int sort_index = array->GetSortedKeyIndex(low);
Name entry = array->GetKey(InternalIndex(sort_index));
- uint32_t current_hash = entry.hash_field();
+ uint32_t current_hash = entry.hash();
if (current_hash != hash) {
if (search_mode == ALL_ENTRIES && out_insertion_index != nullptr) {
*out_insertion_index = sort_index + (current_hash > hash ? 0 : 1);
@@ -259,12 +259,12 @@ template <SearchMode search_mode, typename T>
int LinearSearch(T* array, Name name, int valid_entries,
int* out_insertion_index) {
if (search_mode == ALL_ENTRIES && out_insertion_index != nullptr) {
- uint32_t hash = name.hash_field();
+ uint32_t hash = name.hash();
int len = array->number_of_entries();
for (int number = 0; number < len; number++) {
int sorted_index = array->GetSortedKeyIndex(number);
Name entry = array->GetKey(InternalIndex(sorted_index));
- uint32_t current_hash = entry.hash_field();
+ uint32_t current_hash = entry.hash();
if (current_hash > hash) {
*out_insertion_index = sorted_index;
return T::kNotFound;
diff --git a/deps/v8/src/objects/name-inl.h b/deps/v8/src/objects/name-inl.h
index 0735b4e506f..ffcd287fd37 100644
--- a/deps/v8/src/objects/name-inl.h
+++ b/deps/v8/src/objects/name-inl.h
@@ -94,6 +94,12 @@ uint32_t Name::Hash() {
return String::cast(*this).ComputeAndSetHash();
}
+uint32_t Name::hash() const {
+ uint32_t field = hash_field();
+ DCHECK(IsHashFieldComputed(field));
+ return field >> kHashShift;
+}
+
DEF_GETTER(Name, IsInterestingSymbol, bool) {
return IsSymbol(isolate) && Symbol::cast(*this).is_interesting_symbol();
}
diff --git a/deps/v8/src/objects/name.h b/deps/v8/src/objects/name.h
index 533d8b000eb..6309de9d4ca 100644
--- a/deps/v8/src/objects/name.h
+++ b/deps/v8/src/objects/name.h
@@ -23,9 +23,15 @@ class Name : public TorqueGeneratedName<Name, PrimitiveHeapObject> {
// Tells whether the hash code has been computed.
inline bool HasHashCode();
- // Returns a hash value used for the property table
+ // Returns a hash value used for the property table. Ensures that the hash
+ // value is computed.
+ // TODO(ishell): rename to EnsureHash().
inline uint32_t Hash();
+ // Returns a hash value used for the property table (same as Hash()), assumes
+ // the hash is already computed.
+ inline uint32_t hash() const;
+
// Equality operations.
inline bool Equals(Name other);
inline static bool Equals(Isolate* isolate, Handle<Name> one,
diff --git a/deps/v8/src/objects/objects.cc b/deps/v8/src/objects/objects.cc
index 3eb78f46301..009b09284e6 100644
--- a/deps/v8/src/objects/objects.cc
+++ b/deps/v8/src/objects/objects.cc
@@ -4355,16 +4355,16 @@ void DescriptorArray::Sort() {
// Reset sorting since the descriptor array might contain invalid pointers.
for (int i = 0; i < len; ++i) SetSortedKey(i, i);
// Bottom-up max-heap construction.
- // Index of the last node with children
+ // Index of the last node with children.
const int max_parent_index = (len / 2) - 1;
for (int i = max_parent_index; i >= 0; --i) {
int parent_index = i;
- const uint32_t parent_hash = GetSortedKey(i).Hash();
+ const uint32_t parent_hash = GetSortedKey(i).hash();
while (parent_index <= max_parent_index) {
int child_index = 2 * parent_index + 1;
- uint32_t child_hash = GetSortedKey(child_index).Hash();
+ uint32_t child_hash = GetSortedKey(child_index).hash();
if (child_index + 1 < len) {
- uint32_t right_child_hash = GetSortedKey(child_index + 1).Hash();
+ uint32_t right_child_hash = GetSortedKey(child_index + 1).hash();
if (right_child_hash > child_hash) {
child_index++;
child_hash = right_child_hash;
@@ -4383,13 +4383,13 @@ void DescriptorArray::Sort() {
SwapSortedKeys(0, i);
// Shift down the new top element.
int parent_index = 0;
- const uint32_t parent_hash = GetSortedKey(parent_index).Hash();
+ const uint32_t parent_hash = GetSortedKey(parent_index).hash();
const int max_parent_index = (i / 2) - 1;
while (parent_index <= max_parent_index) {
int child_index = parent_index * 2 + 1;
- uint32_t child_hash = GetSortedKey(child_index).Hash();
+ uint32_t child_hash = GetSortedKey(child_index).hash();
if (child_index + 1 < i) {
- uint32_t right_child_hash = GetSortedKey(child_index + 1).Hash();
+ uint32_t right_child_hash = GetSortedKey(child_index + 1).hash();
if (right_child_hash > child_hash) {
child_index++;
child_hash = right_child_hash;
diff --git a/deps/v8/src/objects/transitions-inl.h b/deps/v8/src/objects/transitions-inl.h
index 5694d66d948..09157b7f5d0 100644
--- a/deps/v8/src/objects/transitions-inl.h
+++ b/deps/v8/src/objects/transitions-inl.h
@@ -169,12 +169,20 @@ int TransitionArray::SearchNameForTesting(Name name, int* out_insertion_index) {
return SearchName(name, out_insertion_index);
}
+Map TransitionArray::SearchAndGetTargetForTesting(
+ PropertyKind kind, Name name, PropertyAttributes attributes) {
+ return SearchAndGetTarget(kind, name, attributes);
+}
+
int TransitionArray::SearchSpecial(Symbol symbol, int* out_insertion_index) {
return SearchName(symbol, out_insertion_index);
}
int TransitionArray::SearchName(Name name, int* out_insertion_index) {
DCHECK(name.IsUniqueName());
+ // The name is taken from DescriptorArray, so it must already has a computed
+ // hash.
+ DCHECK(name.HasHashCode());
return internal::Search<ALL_ENTRIES>(this, name, number_of_entries(),
out_insertion_index);
}
diff --git a/deps/v8/src/objects/transitions.cc b/deps/v8/src/objects/transitions.cc
index e0ba40ce7d0..e240878b33d 100644
--- a/deps/v8/src/objects/transitions.cc
+++ b/deps/v8/src/objects/transitions.cc
@@ -619,8 +619,8 @@ void TransitionArray::Sort() {
temp_kind = details.kind();
temp_attributes = details.attributes();
}
- int cmp = CompareKeys(temp_key, temp_key.Hash(), temp_kind,
- temp_attributes, key, key.Hash(), kind, attributes);
+ int cmp = CompareKeys(temp_key, temp_key.hash(), temp_kind,
+ temp_attributes, key, key.hash(), kind, attributes);
if (cmp > 0) {
SetKey(j + 1, temp_key);
SetRawTarget(j + 1, temp_target);
diff --git a/deps/v8/src/objects/transitions.h b/deps/v8/src/objects/transitions.h
index 5a7db13e516..055bf41c914 100644
--- a/deps/v8/src/objects/transitions.h
+++ b/deps/v8/src/objects/transitions.h
@@ -143,6 +143,8 @@ class V8_EXPORT_PRIVATE TransitionsAccessor {
return encoding_;
}
+ inline TransitionArray transitions();
+
private:
friend class MarkCompactCollector; // For HasSimpleTransitionTo.
friend class TransitionArray;
@@ -175,8 +177,6 @@ class V8_EXPORT_PRIVATE TransitionsAccessor {
void TraverseTransitionTreeInternal(TraverseCallback callback, void* data,
DisallowHeapAllocation* no_gc);
- inline TransitionArray transitions();
-
Isolate* isolate_;
Handle<Map> map_handle_;
Map map_;
@@ -231,7 +231,7 @@ class TransitionArray : public WeakFixedArray {
V8_EXPORT_PRIVATE bool IsSortedNoDuplicates(int valid_entries = -1);
#endif
- void Sort();
+ V8_EXPORT_PRIVATE void Sort();
void PrintInternal(std::ostream& os);
@@ -260,6 +260,9 @@ class TransitionArray : public WeakFixedArray {
inline int SearchNameForTesting(Name name,
int* out_insertion_index = nullptr);
+ inline Map SearchAndGetTargetForTesting(PropertyKind kind, Name name,
+ PropertyAttributes attributes);
+
private:
friend class Factory;
friend class MarkCompactCollector;
@@ -296,8 +299,8 @@ class TransitionArray : public WeakFixedArray {
int Search(PropertyKind kind, Name name, PropertyAttributes attributes,
int* out_insertion_index = nullptr);
- Map SearchAndGetTarget(PropertyKind kind, Name name,
- PropertyAttributes attributes);
+ V8_EXPORT_PRIVATE Map SearchAndGetTarget(PropertyKind kind, Name name,
+ PropertyAttributes attributes);
// Search a non-property transition (like elements kind, observe or frozen
// transitions).
diff --git a/deps/v8/test/cctest/BUILD.gn b/deps/v8/test/cctest/BUILD.gn
index 2c9363130a3..94e9e73c0e6 100644
--- a/deps/v8/test/cctest/BUILD.gn
+++ b/deps/v8/test/cctest/BUILD.gn
@@ -204,6 +204,7 @@ v8_source_set("cctest_sources") {
"test-debug.cc",
"test-decls.cc",
"test-deoptimization.cc",
+ "test-descriptor-array.cc",
"test-dictionary.cc",
"test-diy-fp.cc",
"test-double.cc",
diff --git a/deps/v8/test/cctest/test-descriptor-array.cc b/deps/v8/test/cctest/test-descriptor-array.cc
new file mode 100644
index 00000000000..9a7b9bc1295
--- /dev/null
+++ b/deps/v8/test/cctest/test-descriptor-array.cc
@@ -0,0 +1,424 @@
+// 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();
+ 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().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().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.
+ Code::STUB);
+ {
+ CodeStubAssembler m(asm_tester.state());
+
+ TNode<Map> map = m.CAST(m.Parameter(1));
+ TNode<Name> unique_name = m.CAST(m.Parameter(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.location()) = ft.function->ptr();
+ }
+
+ 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.
+ Code::STUB);
+ {
+ CodeStubAssembler m(asm_tester.state());
+
+ TNode<TransitionArray> transitions = m.CAST(m.Parameter(1));
+ TNode<Name> unique_name = m.CAST(m.Parameter(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.location()) = ft.function->ptr();
+ }
+
+ 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().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().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
diff --git a/deps/v8/test/cctest/test-transitions.h b/deps/v8/test/cctest/test-transitions.h
index 724eb3d3c54..66bbbfa76dd 100644
--- a/deps/v8/test/cctest/test-transitions.h
+++ b/deps/v8/test/cctest/test-transitions.h
@@ -24,6 +24,8 @@ class TestTransitionsAccessor : public TransitionsAccessor {
bool IsFullTransitionArrayEncoding() {
return encoding() == kFullTransitionArray;
}
+
+ TransitionArray transitions() { return TransitionsAccessor::transitions(); }
};
} // namespace internal