Skip to content

Commit 518d67a

Browse files
isheludkoCommit Bot
isheludko
authored and
Commit Bot
committed
[runtime] Fix sorted order of DescriptorArray entries
... and add respective regression tests. This CL also adds similar regression tests for TransitionArray but it doesn't have the same issue as DescriptorArray. Bug: chromium:1133527 Change-Id: I668a90f126d76af0a39816ce8697cb29bc65d01b Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2465833 Reviewed-by: Toon Verwaest <[email protected]> Commit-Queue: Igor Sheludko <[email protected]> Cr-Commit-Position: refs/heads/master@{#70570}
1 parent f4376ec commit 518d67a

15 files changed

Lines changed: 487 additions & 35 deletions

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

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1832,12 +1832,13 @@ TNode<IntPtrT> CodeStubAssembler::LoadJSReceiverIdentityHash(
18321832
return var_hash.value();
18331833
}
18341834

1835-
TNode<Uint32T> CodeStubAssembler::LoadNameHashField(SloppyTNode<Name> name) {
1836-
CSA_ASSERT(this, IsName(name));
1837-
return LoadObjectField<Uint32T>(name, Name::kHashFieldOffset);
1835+
TNode<Uint32T> CodeStubAssembler::LoadNameHashAssumeComputed(TNode<Name> name) {
1836+
TNode<Uint32T> hash_field = LoadNameHashField(name);
1837+
CSA_ASSERT(this, IsClearWord32(hash_field, Name::kHashNotComputedMask));
1838+
return Unsigned(Word32Shr(hash_field, Int32Constant(Name::kHashShift)));
18381839
}
18391840

1840-
TNode<Uint32T> CodeStubAssembler::LoadNameHash(SloppyTNode<Name> name,
1841+
TNode<Uint32T> CodeStubAssembler::LoadNameHash(TNode<Name> name,
18411842
Label* if_hash_not_computed) {
18421843
TNode<Uint32T> hash_field = LoadNameHashField(name);
18431844
if (if_hash_not_computed != nullptr) {
@@ -8110,7 +8111,7 @@ void CodeStubAssembler::LookupBinary(TNode<Name> unique_name,
81108111
TNode<Uint32T> limit =
81118112
Unsigned(Int32Sub(NumberOfEntries<Array>(array), Int32Constant(1)));
81128113
TVARIABLE(Uint32T, var_high, limit);
8113-
TNode<Uint32T> hash = LoadNameHashField(unique_name);
8114+
TNode<Uint32T> hash = LoadNameHashAssumeComputed(unique_name);
81148115
CSA_ASSERT(this, Word32NotEqual(hash, Int32Constant(0)));
81158116

81168117
// Assume non-empty array.
@@ -8128,7 +8129,7 @@ void CodeStubAssembler::LookupBinary(TNode<Name> unique_name,
81288129
TNode<Uint32T> sorted_key_index = GetSortedKeyIndex<Array>(array, mid);
81298130
TNode<Name> mid_name = GetKey<Array>(array, sorted_key_index);
81308131

8131-
TNode<Uint32T> mid_hash = LoadNameHashField(mid_name);
8132+
TNode<Uint32T> mid_hash = LoadNameHashAssumeComputed(mid_name);
81328133

81338134
Label mid_greater(this), mid_less(this), merge(this);
81348135
Branch(Uint32GreaterThanOrEqual(mid_hash, hash), &mid_greater, &mid_less);
@@ -8155,7 +8156,7 @@ void CodeStubAssembler::LookupBinary(TNode<Name> unique_name,
81558156
TNode<Uint32T> sort_index =
81568157
GetSortedKeyIndex<Array>(array, var_low.value());
81578158
TNode<Name> current_name = GetKey<Array>(array, sort_index);
8158-
TNode<Uint32T> current_hash = LoadNameHashField(current_name);
8159+
TNode<Uint32T> current_hash = LoadNameHashAssumeComputed(current_name);
81598160
GotoIf(Word32NotEqual(current_hash, hash), if_not_found);
81608161
Label next(this);
81618162
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
@@ -1268,13 +1268,12 @@ class V8_EXPORT_PRIVATE CodeStubAssembler
12681268
// Check if the map is set for slow properties.
12691269
TNode<BoolT> IsDictionaryMap(SloppyTNode<Map> map);
12701270

1271-
// Load the hash field of a name as an uint32 value.
1272-
TNode<Uint32T> LoadNameHashField(SloppyTNode<Name> name);
1273-
// Load the hash value of a name as an uint32 value.
1271+
// Load the Name::hash() value of a name as an uint32 value.
12741272
// If {if_hash_not_computed} label is specified then it also checks if
12751273
// hash is actually computed.
1276-
TNode<Uint32T> LoadNameHash(SloppyTNode<Name> name,
1274+
TNode<Uint32T> LoadNameHash(TNode<Name> name,
12771275
Label* if_hash_not_computed = nullptr);
1276+
TNode<Uint32T> LoadNameHashAssumeComputed(TNode<Name> name);
12781277

12791278
// Load length field of a String object as Smi value.
12801279
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
@@ -1726,12 +1726,13 @@ bool DescriptorArray::IsSortedNoDuplicates() {
17261726
uint32_t current = 0;
17271727
for (int i = 0; i < number_of_descriptors(); i++) {
17281728
Name key = GetSortedKey(i);
1729+
CHECK(key.HasHashCode());
17291730
if (key == current_key) {
17301731
Print();
17311732
return false;
17321733
}
17331734
current_key = key;
1734-
uint32_t hash = GetSortedKey(i).Hash();
1735+
uint32_t hash = key.hash();
17351736
if (hash < current) {
17361737
Print();
17371738
return false;
@@ -1749,7 +1750,8 @@ bool TransitionArray::IsSortedNoDuplicates() {
17491750

17501751
for (int i = 0; i < number_of_transitions(); i++) {
17511752
Name key = GetSortedKey(i);
1752-
uint32_t hash = key.Hash();
1753+
CHECK(key.HasHashCode());
1754+
uint32_t hash = key.hash();
17531755
PropertyKind kind = kData;
17541756
PropertyAttributes attributes = NONE;
17551757
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
@@ -227,7 +227,7 @@ void DescriptorArray::Append(Descriptor* desc) {
227227

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

‎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
@@ -233,15 +233,15 @@ int BinarySearch(T* array, Name name, int valid_entries,
233233
// index). After doing the binary search and getting the correct internal
234234
// index we check to have the index lower than valid_entries, if needed.
235235
int high = array->number_of_entries() - 1;
236-
uint32_t hash = name.hash_field();
236+
uint32_t hash = name.hash();
237237
int limit = high;
238238

239239
DCHECK(low <= high);
240240

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

246246
if (mid_hash >= hash) {
247247
high = mid;
@@ -253,7 +253,7 @@ int BinarySearch(T* array, Name name, int valid_entries,
253253
for (; low <= limit; ++low) {
254254
int sort_index = array->GetSortedKeyIndex(low);
255255
Name entry = array->GetKey(InternalIndex(sort_index));
256-
uint32_t current_hash = entry.hash_field();
256+
uint32_t current_hash = entry.hash();
257257
if (current_hash != hash) {
258258
// 'search_mode == ALL_ENTRIES' here and below is not needed since
259259
// 'out_insertion_index != nullptr' implies 'search_mode == ALL_ENTRIES'.
@@ -285,12 +285,12 @@ template <SearchMode search_mode, typename T>
285285
int LinearSearch(T* array, Name name, int valid_entries,
286286
int* out_insertion_index) {
287287
if (search_mode == ALL_ENTRIES && out_insertion_index != nullptr) {
288-
uint32_t hash = name.hash_field();
288+
uint32_t hash = name.hash();
289289
int len = array->number_of_entries();
290290
for (int number = 0; number < len; number++) {
291291
int sorted_index = array->GetSortedKeyIndex(number);
292292
Name entry = array->GetKey(InternalIndex(sorted_index));
293-
uint32_t current_hash = entry.hash_field();
293+
uint32_t current_hash = entry.hash();
294294
if (current_hash > hash) {
295295
*out_insertion_index = sorted_index;
296296
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
@@ -4362,16 +4362,16 @@ void DescriptorArray::Sort() {
43624362
// Reset sorting since the descriptor array might contain invalid pointers.
43634363
for (int i = 0; i < len; ++i) SetSortedKey(i, i);
43644364
// Bottom-up max-heap construction.
4365-
// Index of the last node with children
4365+
// Index of the last node with children.
43664366
const int max_parent_index = (len / 2) - 1;
43674367
for (int i = max_parent_index; i >= 0; --i) {
43684368
int parent_index = i;
4369-
const uint32_t parent_hash = GetSortedKey(i).Hash();
4369+
const uint32_t parent_hash = GetSortedKey(i).hash();
43704370
while (parent_index <= max_parent_index) {
43714371
int child_index = 2 * parent_index + 1;
4372-
uint32_t child_hash = GetSortedKey(child_index).Hash();
4372+
uint32_t child_hash = GetSortedKey(child_index).hash();
43734373
if (child_index + 1 < len) {
4374-
uint32_t right_child_hash = GetSortedKey(child_index + 1).Hash();
4374+
uint32_t right_child_hash = GetSortedKey(child_index + 1).hash();
43754375
if (right_child_hash > child_hash) {
43764376
child_index++;
43774377
child_hash = right_child_hash;
@@ -4390,13 +4390,13 @@ void DescriptorArray::Sort() {
43904390
SwapSortedKeys(0, i);
43914391
// Shift down the new top element.
43924392
int parent_index = 0;
4393-
const uint32_t parent_hash = GetSortedKey(parent_index).Hash();
4393+
const uint32_t parent_hash = GetSortedKey(parent_index).hash();
43944394
const int max_parent_index = (i / 2) - 1;
43954395
while (parent_index <= max_parent_index) {
43964396
int child_index = parent_index * 2 + 1;
4397-
uint32_t child_hash = GetSortedKey(child_index).Hash();
4397+
uint32_t child_hash = GetSortedKey(child_index).hash();
43984398
if (child_index + 1 < i) {
4399-
uint32_t right_child_hash = GetSortedKey(child_index + 1).Hash();
4399+
uint32_t right_child_hash = GetSortedKey(child_index + 1).hash();
44004400
if (right_child_hash > child_hash) {
44014401
child_index++;
44024402
child_hash = right_child_hash;

‎src/objects/transitions-inl.h‎

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

180+
Map TransitionArray::SearchAndGetTargetForTesting(
181+
PropertyKind kind, Name name, PropertyAttributes attributes) {
182+
return SearchAndGetTarget(kind, name, attributes);
183+
}
184+
180185
int TransitionArray::SearchSpecial(Symbol symbol, int* out_insertion_index) {
181186
return SearchName(symbol, out_insertion_index);
182187
}
183188

184189
int TransitionArray::SearchName(Name name, int* out_insertion_index) {
185190
DCHECK(name.IsUniqueName());
191+
// The name is taken from DescriptorArray, so it must already has a computed
192+
// hash.
193+
DCHECK(name.HasHashCode());
186194
return internal::Search<ALL_ENTRIES>(this, name, number_of_entries(),
187195
out_insertion_index);
188196
}

0 commit comments

Comments
 (0)