Skip to content

Commit e3f4d6a

Browse files
joyeecheungaduh95
joyeecheung
authored and
aduh95
committed
deps: V8: backport 1361b2a49d02
Original commit message: [strings] improve array index hash distribution Previously, the hashes stored in a Name's raw_hash_field for decimal numeric strings (potential array indices) consist of the literal integer value along with the length of the string. This means consecutive numeric strings can have consecutive hash values, which can lead to O(n^2) probing for insertion in the worst case when e.g. a non-numeric string happen to land in the these buckets. This patch adds a build-time flag v8_enable_seeded_array_index_hash that scrambles the 24-bit array-index value stored in a Name's raw_hash_field to improve the distribution. x ^= x >> kShift; x = (x * m1) & kMask; // round 1 x ^= x >> kShift; x = (x * m2) & kMask; // round 2 x ^= x >> kShift; // finalize To decode, apply the same steps with the modular inverses of m1 and m2 in reverse order. x ^= x >> kShift; x = (x * m2_inv) & kMask; // round 1 x ^= x >> kShift; x = (x * m1_inv) & kMask; // round 2 x ^= x >> kShift; // finalize where kShift = kArrayIndexValueBits / 2, kMask = kArrayIndexValueMask, m1, m2 (both odd) are the lower bits of the rapidhash secrets, m1_inv, m2_inv (modular inverses) are precomputed modular inverse of m1 and m2. The pre-computed values are appended to the hash_seed ByteArray in ReadOnlyRoots and accessed in generated code to reduce overhead. In call sites that don't already have access to the seeds, we read them from the current isolate group/isolate's read only roots. To consolidate the code that encode/decode these hashes, this patch adds MakeArrayIndexHash/DecodeArrayIndexFromHashField in C++ and CSA that perform seeding/unseeding if enabled, and updates places where encoding/decoding of array index is needed to use them. Bug: 477515021 Change-Id: I350afe511951a54c4378396538152cc56565fd55 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7564330 Reviewed-by: Leszek Swirski <[email protected]> Commit-Queue: Joyee Cheung <[email protected]> Cr-Commit-Position: refs/heads/main@{#105596} Refs: v8/v8@1361b2a Co-authored-by: Joyee Cheung <[email protected]> Backport-PR-URL: nodejs-private/node-private#833 Reviewed-By: Antoine du Hamel <[email protected]> PR-URL: nodejs-private/node-private#809 CVE-ID: CVE-2026-21717
1 parent 7dc00fa commit e3f4d6a

25 files changed

+425
-70
lines changed

‎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.37',
41+
'v8_embedder_string': '-node.38',
4242

4343
##### V8 defaults for Node.js #####
4444

‎deps/v8/BUILD.bazel‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -211,6 +211,11 @@ v8_flag(
211211
default = False,
212212
)
213213

214+
v8_flag(
215+
name = "v8_enable_seeded_array_index_hash",
216+
default = False,
217+
)
218+
214219
v8_int(
215220
name = "v8_typed_array_max_size_in_heap",
216221
default = 64,
@@ -421,6 +426,7 @@ v8_config(
421426
"v8_enable_verify_heap": "VERIFY_HEAP",
422427
"v8_enable_verify_predictable": "VERIFY_PREDICTABLE",
423428
"v8_enable_webassembly": "V8_ENABLE_WEBASSEMBLY",
429+
"v8_enable_seeded_array_index_hash": "V8_ENABLE_SEEDED_ARRAY_INDEX_HASH",
424430
"v8_jitless": "V8_JITLESS",
425431
"v8_enable_vtunejit": "ENABLE_VTUNE_JIT_INTERFACE",
426432
},

‎deps/v8/BUILD.gn‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -431,6 +431,9 @@ declare_args() {
431431

432432
# Use a hard-coded secret value when hashing.
433433
v8_use_default_hasher_secret = true
434+
435+
# Enable seeded array index hash.
436+
v8_enable_seeded_array_index_hash = false
434437
}
435438

436439
# Derived defaults.
@@ -1050,6 +1053,9 @@ config("features") {
10501053
if (v8_enable_lite_mode) {
10511054
defines += [ "V8_LITE_MODE" ]
10521055
}
1056+
if (v8_enable_seeded_array_index_hash) {
1057+
defines += [ "V8_ENABLE_SEEDED_ARRAY_INDEX_HASH" ]
1058+
}
10531059
if (v8_enable_gdbjit) {
10541060
defines += [ "ENABLE_GDB_JIT_INTERFACE" ]
10551061
}

‎deps/v8/src/ast/ast-value-factory.cc‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -82,7 +82,8 @@ bool AstRawString::AsArrayIndex(uint32_t* index) const {
8282
// can't be convertible to an array index.
8383
if (!IsIntegerIndex()) return false;
8484
if (length() <= Name::kMaxCachedArrayIndexLength) {
85-
*index = Name::ArrayIndexValueBits::decode(raw_hash_field_);
85+
*index = StringHasher::DecodeArrayIndexFromHashField(
86+
raw_hash_field_, HashSeed(ReadOnlyHeap::GetReadOnlyRoots()));
8687
return true;
8788
}
8889
// Might be an index, but too big to cache it. Do the slow conversion. This

‎deps/v8/src/builtins/number.tq‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -300,7 +300,7 @@ transitioning javascript builtin NumberParseFloat(
300300
const hash: NameHash = s.raw_hash_field;
301301
if (IsIntegerIndex(hash) &&
302302
hash.array_index_length < kMaxCachedArrayIndexLength) {
303-
const arrayIndex: uint32 = hash.array_index_value;
303+
const arrayIndex: uint32 = DecodeArrayIndexFromHashField(hash);
304304
return SmiFromUint32(arrayIndex);
305305
}
306306
// Fall back to the runtime to convert string to a number.
@@ -351,7 +351,7 @@ transitioning builtin ParseInt(
351351
const hash: NameHash = s.raw_hash_field;
352352
if (IsIntegerIndex(hash) &&
353353
hash.array_index_length < kMaxCachedArrayIndexLength) {
354-
const arrayIndex: uint32 = hash.array_index_value;
354+
const arrayIndex: uint32 = DecodeArrayIndexFromHashField(hash);
355355
return SmiFromUint32(arrayIndex);
356356
}
357357
// Fall back to the runtime.

‎deps/v8/src/builtins/wasm.tq‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1406,8 +1406,8 @@ builtin WasmStringToDouble(s: String): float64 {
14061406
const hash: NameHash = s.raw_hash_field;
14071407
if (IsIntegerIndex(hash) &&
14081408
hash.array_index_length < kMaxCachedArrayIndexLength) {
1409-
const arrayIndex: int32 = Signed(hash.array_index_value);
1410-
return Convert<float64>(arrayIndex);
1409+
const arrayIndex: uint32 = DecodeArrayIndexFromHashField(hash);
1410+
return Convert<float64>(Signed(arrayIndex));
14111411
}
14121412
return StringToFloat64(Flatten(s));
14131413
}

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

Lines changed: 53 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2392,6 +2392,56 @@ TNode<Uint32T> CodeStubAssembler::LoadJSReceiverIdentityHash(
23922392
return var_hash.value();
23932393
}
23942394

2395+
#ifdef V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
2396+
// Mirror C++ StringHasher::SeedArrayIndexValue.
2397+
TNode<Uint32T> CodeStubAssembler::SeedArrayIndexValue(TNode<Uint32T> value) {
2398+
// Load m1 and m2 from the hash seed byte array. In the compiled code
2399+
// these will always come from the read-only roots.
2400+
TNode<ByteArray> hash_seed = CAST(LoadRoot(RootIndex::kHashSeed));
2401+
intptr_t base_offset = ByteArray::kHeaderSize - kHeapObjectTag;
2402+
TNode<Uint32T> m1 = Load<Uint32T>(
2403+
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM1Offset));
2404+
TNode<Uint32T> m2 = Load<Uint32T>(
2405+
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM2Offset));
2406+
2407+
TNode<Word32T> x = value;
2408+
// 2-round xorshift-multiply.
2409+
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
2410+
x = Word32And(Uint32Mul(Unsigned(x), m1),
2411+
Uint32Constant(Name::kArrayIndexValueMask));
2412+
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
2413+
x = Word32And(Uint32Mul(Unsigned(x), m2),
2414+
Uint32Constant(Name::kArrayIndexValueMask));
2415+
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
2416+
2417+
return Unsigned(x);
2418+
}
2419+
2420+
// Mirror C++ StringHasher::UnseedArrayIndexValue.
2421+
TNode<Uint32T> CodeStubAssembler::UnseedArrayIndexValue(TNode<Uint32T> value) {
2422+
// Load m1_inv and m2_inv from the hash seed byte array. In the compiled code
2423+
// these will always come from the read-only roots.
2424+
TNode<ByteArray> hash_seed = CAST(LoadRoot(RootIndex::kHashSeed));
2425+
intptr_t base_offset = ByteArray::kHeaderSize - kHeapObjectTag;
2426+
TNode<Uint32T> m1_inv = Load<Uint32T>(
2427+
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM1InvOffset));
2428+
TNode<Uint32T> m2_inv = Load<Uint32T>(
2429+
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM2InvOffset));
2430+
2431+
TNode<Word32T> x = value;
2432+
// 2-round xorshift-multiply (inverse).
2433+
// Xorshift is an involution when kShift is at least half of the value width.
2434+
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
2435+
x = Word32And(Uint32Mul(Unsigned(x), m2_inv),
2436+
Uint32Constant(Name::kArrayIndexValueMask));
2437+
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
2438+
x = Word32And(Uint32Mul(Unsigned(x), m1_inv),
2439+
Uint32Constant(Name::kArrayIndexValueMask));
2440+
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
2441+
return Unsigned(x);
2442+
}
2443+
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
2444+
23952445
TNode<Uint32T> CodeStubAssembler::LoadNameHashAssumeComputed(TNode<Name> name) {
23962446
TNode<Uint32T> hash_field = LoadNameRawHash(name);
23972447
CSA_DCHECK(this, IsClearWord32(hash_field, Name::kHashNotComputedMask));
@@ -8334,8 +8384,7 @@ TNode<Number> CodeStubAssembler::StringToNumber(TNode<String> input) {
83348384
GotoIf(IsSetWord32(raw_hash_field, Name::kDoesNotContainCachedArrayIndexMask),
83358385
&runtime);
83368386

8337-
var_result = SmiTag(Signed(
8338-
DecodeWordFromWord32<String::ArrayIndexValueBits>(raw_hash_field)));
8387+
var_result = SmiFromUint32(DecodeArrayIndexFromHashField(raw_hash_field));
83398388
Goto(&end);
83408389

83418390
BIND(&runtime);
@@ -9251,9 +9300,8 @@ void CodeStubAssembler::TryToName(TNode<Object> key, Label* if_keyisindex,
92519300

92529301
BIND(&if_has_cached_index);
92539302
{
9254-
TNode<IntPtrT> index =
9255-
Signed(DecodeWordFromWord32<String::ArrayIndexValueBits>(
9256-
raw_hash_field));
9303+
TNode<IntPtrT> index = Signed(ChangeUint32ToWord(
9304+
DecodeArrayIndexFromHashField(raw_hash_field)));
92579305
CSA_DCHECK(this, IntPtrLessThan(index, IntPtrConstant(INT_MAX)));
92589306
*var_index = index;
92599307
Goto(if_keyisindex);

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

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4714,6 +4714,12 @@ class V8_EXPORT_PRIVATE CodeStubAssembler
47144714
TNode<Int32T> num_args,
47154715
TNode<FixedArray> args);
47164716

4717+
#ifdef V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
4718+
// Mirror C++ StringHasher::SeedArrayIndexValue and UnseedArrayIndexValue.
4719+
TNode<Uint32T> SeedArrayIndexValue(TNode<Uint32T> value);
4720+
TNode<Uint32T> UnseedArrayIndexValue(TNode<Uint32T> value);
4721+
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
4722+
47174723
private:
47184724
friend class CodeStubArguments;
47194725

‎deps/v8/src/heap/factory-base.cc‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1077,7 +1077,8 @@ inline Handle<String> FactoryBase<Impl>::SmiToString(Tagged<Smi> number,
10771077
if (raw->raw_hash_field() == String::kEmptyHashField &&
10781078
number.value() >= 0) {
10791079
uint32_t raw_hash_field = StringHasher::MakeArrayIndexHash(
1080-
static_cast<uint32_t>(number.value()), raw->length());
1080+
static_cast<uint32_t>(number.value()), raw->length(),
1081+
HashSeed(read_only_roots()));
10811082
raw->set_raw_hash_field(raw_hash_field);
10821083
}
10831084
}

‎deps/v8/src/heap/factory.cc‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3678,7 +3678,8 @@ Handle<String> Factory::SizeToString(size_t value, bool check_cache) {
36783678
if (value <= JSArray::kMaxArrayIndex &&
36793679
raw->raw_hash_field() == String::kEmptyHashField) {
36803680
uint32_t raw_hash_field = StringHasher::MakeArrayIndexHash(
3681-
static_cast<uint32_t>(value), raw->length());
3681+
static_cast<uint32_t>(value), raw->length(),
3682+
HashSeed(read_only_roots()));
36823683
raw->set_raw_hash_field(raw_hash_field);
36833684
}
36843685
}

0 commit comments

Comments
 (0)