Skip to content

Commit 1a7d55a

Browse files
isheludkoisheludko
committed
Merged: [runtime] Fix sorted order of DescriptorArray entries
Revision: 518d67a 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: a64aed2-refs/heads/8.6.395@{#1} Cr-Branched-From: a626bc0-refs/heads/master@{#69472}
1 parent 58bdafe commit 1a7d55a

15 files changed

Lines changed: 489 additions & 37 deletions

‎src/codegen/code-stub-assembler.cc‎

Lines changed: 10 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1754,12 +1754,13 @@ TNode<IntPtrT> CodeStubAssembler::LoadJSReceiverIdentityHash(
17541754
return var_hash.value();
17551755
}
17561756

1757-
TNode<Uint32T> CodeStubAssembler::LoadNameHashField(SloppyTNode<Name> name) {
1758-
CSA_ASSERT(this, IsName(name));
1759-
return LoadObjectField<Uint32T>(name, Name::kHashFieldOffset);
1757+
TNode<Uint32T> CodeStubAssembler::LoadNameHashAssumeComputed(TNode<Name> name) {
1758+
TNode<Uint32T> hash_field = LoadNameHashField(name);
1759+
CSA_ASSERT(this, IsClearWord32(hash_field, Name::kHashNotComputedMask));
1760+
return Unsigned(Word32Shr(hash_field, Int32Constant(Name::kHashShift)));
17601761
}
17611762

1762-
TNode<Uint32T> CodeStubAssembler::LoadNameHash(SloppyTNode<Name> name,
1763+
TNode<Uint32T> CodeStubAssembler::LoadNameHash(TNode<Name> name,
17631764
Label* if_hash_not_computed) {
17641765
TNode<Uint32T> hash_field = LoadNameHashField(name);
17651766
if (if_hash_not_computed != nullptr) {
@@ -1947,13 +1948,13 @@ TNode<T> CodeStubAssembler::LoadArrayElement(TNode<Array> array,
19471948
}
19481949
}
19491950

1950-
template TNode<MaybeObject>
1951+
template V8_EXPORT_PRIVATE TNode<MaybeObject>
19511952
CodeStubAssembler::LoadArrayElement<TransitionArray>(TNode<TransitionArray>,
19521953
int, Node*, int,
19531954
ParameterMode,
19541955
LoadSensitivity);
19551956

1956-
template TNode<MaybeObject>
1957+
template V8_EXPORT_PRIVATE TNode<MaybeObject>
19571958
CodeStubAssembler::LoadArrayElement<DescriptorArray>(TNode<DescriptorArray>,
19581959
int, Node*, int,
19591960
ParameterMode,
@@ -7967,7 +7968,7 @@ void CodeStubAssembler::LookupBinary(TNode<Name> unique_name,
79677968
TNode<Uint32T> limit =
79687969
Unsigned(Int32Sub(NumberOfEntries<Array>(array), Int32Constant(1)));
79697970
TVARIABLE(Uint32T, var_high, limit);
7970-
TNode<Uint32T> hash = LoadNameHashField(unique_name);
7971+
TNode<Uint32T> hash = LoadNameHashAssumeComputed(unique_name);
79717972
CSA_ASSERT(this, Word32NotEqual(hash, Int32Constant(0)));
79727973

79737974
// Assume non-empty array.
@@ -7985,7 +7986,7 @@ void CodeStubAssembler::LookupBinary(TNode<Name> unique_name,
79857986
TNode<Uint32T> sorted_key_index = GetSortedKeyIndex<Array>(array, mid);
79867987
TNode<Name> mid_name = GetKey<Array>(array, sorted_key_index);
79877988

7988-
TNode<Uint32T> mid_hash = LoadNameHashField(mid_name);
7989+
TNode<Uint32T> mid_hash = LoadNameHashAssumeComputed(mid_name);
79897990

79907991
Label mid_greater(this), mid_less(this), merge(this);
79917992
Branch(Uint32GreaterThanOrEqual(mid_hash, hash), &mid_greater, &mid_less);
@@ -8012,7 +8013,7 @@ void CodeStubAssembler::LookupBinary(TNode<Name> unique_name,
80128013
TNode<Uint32T> sort_index =
80138014
GetSortedKeyIndex<Array>(array, var_low.value());
80148015
TNode<Name> current_name = GetKey<Array>(array, sort_index);
8015-
TNode<Uint32T> current_hash = LoadNameHashField(current_name);
8016+
TNode<Uint32T> current_hash = LoadNameHashAssumeComputed(current_name);
80168017
GotoIf(Word32NotEqual(current_hash, hash), if_not_found);
80178018
Label next(this);
80188019
GotoIf(TaggedNotEqual(current_name, unique_name), &next);

‎src/codegen/code-stub-assembler.h‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1240,13 +1240,12 @@ class V8_EXPORT_PRIVATE CodeStubAssembler
12401240
// Check if the map is set for slow properties.
12411241
TNode<BoolT> IsDictionaryMap(SloppyTNode<Map> map);
12421242

1243-
// Load the hash field of a name as an uint32 value.
1244-
TNode<Uint32T> LoadNameHashField(SloppyTNode<Name> name);
1245-
// Load the hash value of a name as an uint32 value.
1243+
// Load the Name::hash() value of a name as an uint32 value.
12461244
// If {if_hash_not_computed} label is specified then it also checks if
12471245
// hash is actually computed.
1248-
TNode<Uint32T> LoadNameHash(SloppyTNode<Name> name,
1246+
TNode<Uint32T> LoadNameHash(TNode<Name> name,
12491247
Label* if_hash_not_computed = nullptr);
1248+
TNode<Uint32T> LoadNameHashAssumeComputed(TNode<Name> name);
12501249

12511250
// Load length field of a String object as Smi value.
12521251
TNode<Smi> LoadStringLengthAsSmi(TNode<String> string);

‎src/diagnostics/objects-debug.cc‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1702,12 +1702,13 @@ bool DescriptorArray::IsSortedNoDuplicates() {
17021702
uint32_t current = 0;
17031703
for (int i = 0; i < number_of_descriptors(); i++) {
17041704
Name key = GetSortedKey(i);
1705+
CHECK(key.HasHashCode());
17051706
if (key == current_key) {
17061707
Print();
17071708
return false;
17081709
}
17091710
current_key = key;
1710-
uint32_t hash = GetSortedKey(i).Hash();
1711+
uint32_t hash = key.hash();
17111712
if (hash < current) {
17121713
Print();
17131714
return false;
@@ -1725,7 +1726,8 @@ bool TransitionArray::IsSortedNoDuplicates() {
17251726

17261727
for (int i = 0; i < number_of_transitions(); i++) {
17271728
Name key = GetSortedKey(i);
1728-
uint32_t hash = key.Hash();
1729+
CHECK(key.HasHashCode());
1730+
uint32_t hash = key.hash();
17291731
PropertyKind kind = kData;
17301732
PropertyAttributes attributes = NONE;
17311733
if (!TransitionsAccessor::IsSpecialTransition(key.GetReadOnlyRoots(),

‎src/objects/descriptor-array-inl.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -228,7 +228,7 @@ void DescriptorArray::Append(Descriptor* desc) {
228228

229229
for (insertion = descriptor_number; insertion > 0; --insertion) {
230230
Name key = GetSortedKey(insertion - 1);
231-
if (key.Hash() <= hash) break;
231+
if (key.hash() <= hash) break;
232232
SetSortedKey(insertion, GetSortedKeyIndex(insertion - 1));
233233
}
234234

‎src/objects/descriptor-array.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -113,7 +113,7 @@ class DescriptorArray
113113
int slack = 0);
114114

115115
// Sort the instance descriptors by the hash codes of their keys.
116-
void Sort();
116+
V8_EXPORT_PRIVATE void Sort();
117117

118118
// Search the instance descriptors for given name. {concurrent_search} signals
119119
// if we are doing the search on a background thread. If so, we will sacrifice

‎src/objects/fixed-array-inl.h‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -234,15 +234,15 @@ int BinarySearch(T* array, Name name, int valid_entries,
234234
// index). After doing the binary search and getting the correct internal
235235
// index we check to have the index lower than valid_entries, if needed.
236236
int high = array->number_of_entries() - 1;
237-
uint32_t hash = name.hash_field();
237+
uint32_t hash = name.hash();
238238
int limit = high;
239239

240240
DCHECK(low <= high);
241241

242242
while (low != high) {
243243
int mid = low + (high - low) / 2;
244244
Name mid_name = array->GetSortedKey(mid);
245-
uint32_t mid_hash = mid_name.hash_field();
245+
uint32_t mid_hash = mid_name.hash();
246246

247247
if (mid_hash >= hash) {
248248
high = mid;
@@ -254,7 +254,7 @@ int BinarySearch(T* array, Name name, int valid_entries,
254254
for (; low <= limit; ++low) {
255255
int sort_index = array->GetSortedKeyIndex(low);
256256
Name entry = array->GetKey(InternalIndex(sort_index));
257-
uint32_t current_hash = entry.hash_field();
257+
uint32_t current_hash = entry.hash();
258258
if (current_hash != hash) {
259259
// 'search_mode == ALL_ENTRIES' here and below is not needed since
260260
// 'out_insertion_index != nullptr' implies 'search_mode == ALL_ENTRIES'.
@@ -286,12 +286,12 @@ template <SearchMode search_mode, typename T>
286286
int LinearSearch(T* array, Name name, int valid_entries,
287287
int* out_insertion_index) {
288288
if (search_mode == ALL_ENTRIES && out_insertion_index != nullptr) {
289-
uint32_t hash = name.hash_field();
289+
uint32_t hash = name.hash();
290290
int len = array->number_of_entries();
291291
for (int number = 0; number < len; number++) {
292292
int sorted_index = array->GetSortedKeyIndex(number);
293293
Name entry = array->GetKey(InternalIndex(sorted_index));
294-
uint32_t current_hash = entry.hash_field();
294+
uint32_t current_hash = entry.hash();
295295
if (current_hash > hash) {
296296
*out_insertion_index = sorted_index;
297297
return T::kNotFound;

‎src/objects/name-inl.h‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,12 @@ uint32_t Name::Hash() {
9494
return String::cast(*this).ComputeAndSetHash();
9595
}
9696

97+
uint32_t Name::hash() const {
98+
uint32_t field = hash_field();
99+
DCHECK(IsHashFieldComputed(field));
100+
return field >> kHashShift;
101+
}
102+
97103
DEF_GETTER(Name, IsInterestingSymbol, bool) {
98104
return IsSymbol(isolate) && Symbol::cast(*this).is_interesting_symbol();
99105
}

‎src/objects/name.h‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,9 +23,15 @@ class Name : public TorqueGeneratedName<Name, PrimitiveHeapObject> {
2323
// Tells whether the hash code has been computed.
2424
inline bool HasHashCode();
2525

26-
// Returns a hash value used for the property table
26+
// Returns a hash value used for the property table. Ensures that the hash
27+
// value is computed.
28+
// TODO(ishell): rename to EnsureHash().
2729
inline uint32_t Hash();
2830

31+
// Returns a hash value used for the property table (same as Hash()), assumes
32+
// the hash is already computed.
33+
inline uint32_t hash() const;
34+
2935
// Equality operations.
3036
inline bool Equals(Name other);
3137
inline static bool Equals(Isolate* isolate, Handle<Name> one,

‎src/objects/objects.cc‎

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -4347,16 +4347,16 @@ void DescriptorArray::Sort() {
43474347
// Reset sorting since the descriptor array might contain invalid pointers.
43484348
for (int i = 0; i < len; ++i) SetSortedKey(i, i);
43494349
// Bottom-up max-heap construction.
4350-
// Index of the last node with children
4350+
// Index of the last node with children.
43514351
const int max_parent_index = (len / 2) - 1;
43524352
for (int i = max_parent_index; i >= 0; --i) {
43534353
int parent_index = i;
4354-
const uint32_t parent_hash = GetSortedKey(i).Hash();
4354+
const uint32_t parent_hash = GetSortedKey(i).hash();
43554355
while (parent_index <= max_parent_index) {
43564356
int child_index = 2 * parent_index + 1;
4357-
uint32_t child_hash = GetSortedKey(child_index).Hash();
4357+
uint32_t child_hash = GetSortedKey(child_index).hash();
43584358
if (child_index + 1 < len) {
4359-
uint32_t right_child_hash = GetSortedKey(child_index + 1).Hash();
4359+
uint32_t right_child_hash = GetSortedKey(child_index + 1).hash();
43604360
if (right_child_hash > child_hash) {
43614361
child_index++;
43624362
child_hash = right_child_hash;
@@ -4375,13 +4375,13 @@ void DescriptorArray::Sort() {
43754375
SwapSortedKeys(0, i);
43764376
// Shift down the new top element.
43774377
int parent_index = 0;
4378-
const uint32_t parent_hash = GetSortedKey(parent_index).Hash();
4378+
const uint32_t parent_hash = GetSortedKey(parent_index).hash();
43794379
const int max_parent_index = (i / 2) - 1;
43804380
while (parent_index <= max_parent_index) {
43814381
int child_index = parent_index * 2 + 1;
4382-
uint32_t child_hash = GetSortedKey(child_index).Hash();
4382+
uint32_t child_hash = GetSortedKey(child_index).hash();
43834383
if (child_index + 1 < i) {
4384-
uint32_t right_child_hash = GetSortedKey(child_index + 1).Hash();
4384+
uint32_t right_child_hash = GetSortedKey(child_index + 1).hash();
43854385
if (right_child_hash > child_hash) {
43864386
child_index++;
43874387
child_hash = right_child_hash;

‎src/objects/transitions-inl.h‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -169,12 +169,20 @@ int TransitionArray::SearchNameForTesting(Name name, int* out_insertion_index) {
169169
return SearchName(name, out_insertion_index);
170170
}
171171

172+
Map TransitionArray::SearchAndGetTargetForTesting(
173+
PropertyKind kind, Name name, PropertyAttributes attributes) {
174+
return SearchAndGetTarget(kind, name, attributes);
175+
}
176+
172177
int TransitionArray::SearchSpecial(Symbol symbol, int* out_insertion_index) {
173178
return SearchName(symbol, out_insertion_index);
174179
}
175180

176181
int TransitionArray::SearchName(Name name, int* out_insertion_index) {
177182
DCHECK(name.IsUniqueName());
183+
// The name is taken from DescriptorArray, so it must already has a computed
184+
// hash.
185+
DCHECK(name.HasHashCode());
178186
return internal::Search<ALL_ENTRIES>(this, name, number_of_entries(),
179187
out_insertion_index);
180188
}

0 commit comments

Comments
 (0)