Skip to content

Commit 30a3ab1

Browse files
joyeecheungaduh95
joyeecheung
authored and
aduh95
committed
deps: V8: cherry-pick aac14dd95e5b
Original commit message: [string] add 3rd round to seeded array index hash Since we already have 3 derived secrets, and arithmetics are relatively cheap, add a 3rd round to the xorshift-multiply seeding scheme. This brings the bias from ~3.4 to ~0.4. Bug: 477515021 Change-Id: I1ef48954bcee8768d8c90db06ac8adb02f06cebf Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7655117 Reviewed-by: Chengzhong Wu <[email protected]> Commit-Queue: Joyee Cheung <[email protected]> Reviewed-by: Leszek Swirski <[email protected]> Cr-Commit-Position: refs/heads/main@{#105824} Refs: v8/v8@aac14dd 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 6f14ee5 commit 30a3ab1

File tree

7 files changed

+45
-15
lines changed

7 files changed

+45
-15
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.38',
41+
'v8_embedder_string': '-node.39',
4242

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

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

Lines changed: 15 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2395,43 +2395,53 @@ TNode<Uint32T> CodeStubAssembler::LoadJSReceiverIdentityHash(
23952395
#ifdef V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
23962396
// Mirror C++ StringHasher::SeedArrayIndexValue.
23972397
TNode<Uint32T> CodeStubAssembler::SeedArrayIndexValue(TNode<Uint32T> value) {
2398-
// Load m1 and m2 from the hash seed byte array. In the compiled code
2398+
// Load m1, m2 and m3 from the hash seed byte array. In the compiled code
23992399
// these will always come from the read-only roots.
24002400
TNode<ByteArray> hash_seed = CAST(LoadRoot(RootIndex::kHashSeed));
24012401
intptr_t base_offset = ByteArray::kHeaderSize - kHeapObjectTag;
24022402
TNode<Uint32T> m1 = Load<Uint32T>(
24032403
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM1Offset));
24042404
TNode<Uint32T> m2 = Load<Uint32T>(
24052405
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM2Offset));
2406+
TNode<Uint32T> m3 = Load<Uint32T>(
2407+
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM3Offset));
24062408

24072409
TNode<Word32T> x = value;
2408-
// 2-round xorshift-multiply.
2410+
// 3-round xorshift-multiply.
24092411
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
24102412
x = Word32And(Uint32Mul(Unsigned(x), m1),
24112413
Uint32Constant(Name::kArrayIndexValueMask));
24122414
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
24132415
x = Word32And(Uint32Mul(Unsigned(x), m2),
24142416
Uint32Constant(Name::kArrayIndexValueMask));
24152417
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
2418+
x = Word32And(Uint32Mul(Unsigned(x), m3),
2419+
Uint32Constant(Name::kArrayIndexValueMask));
2420+
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
24162421

24172422
return Unsigned(x);
24182423
}
24192424

24202425
// Mirror C++ StringHasher::UnseedArrayIndexValue.
24212426
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.
2427+
// Load m1_inv, m2_inv and m3_inv from the hash seed byte array. In the
2428+
// compiled code these will always come from the read-only roots.
24242429
TNode<ByteArray> hash_seed = CAST(LoadRoot(RootIndex::kHashSeed));
24252430
intptr_t base_offset = ByteArray::kHeaderSize - kHeapObjectTag;
24262431
TNode<Uint32T> m1_inv = Load<Uint32T>(
24272432
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM1InvOffset));
24282433
TNode<Uint32T> m2_inv = Load<Uint32T>(
24292434
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM2InvOffset));
2435+
TNode<Uint32T> m3_inv = Load<Uint32T>(
2436+
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM3InvOffset));
24302437

24312438
TNode<Word32T> x = value;
2432-
// 2-round xorshift-multiply (inverse).
2439+
// 3-round xorshift-multiply (inverse).
24332440
// Xorshift is an involution when kShift is at least half of the value width.
24342441
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
2442+
x = Word32And(Uint32Mul(Unsigned(x), m3_inv),
2443+
Uint32Constant(Name::kArrayIndexValueMask));
2444+
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
24352445
x = Word32And(Uint32Mul(Unsigned(x), m2_inv),
24362446
Uint32Constant(Name::kArrayIndexValueMask));
24372447
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));

‎deps/v8/src/numbers/hash-seed-inl.h‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,8 @@ inline uint32_t HashSeed::m1() const { return data_->m1; }
3131
inline uint32_t HashSeed::m1_inv() const { return data_->m1_inv; }
3232
inline uint32_t HashSeed::m2() const { return data_->m2; }
3333
inline uint32_t HashSeed::m2_inv() const { return data_->m2_inv; }
34+
inline uint32_t HashSeed::m3() const { return data_->m3; }
35+
inline uint32_t HashSeed::m3_inv() const { return data_->m3_inv; }
3436
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
3537

3638
} // namespace internal

‎deps/v8/src/numbers/hash-seed.cc‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,6 +51,8 @@ constexpr void DeriveSecretsForArrayIndexHash(HashSeed::Data* data) {
5151
data->m1_inv = derive_multiplier_inverse(data->secrets[0]);
5252
data->m2 = derive_multiplier(data->secrets[1]);
5353
data->m2_inv = derive_multiplier_inverse(data->secrets[1]);
54+
data->m3 = derive_multiplier(data->secrets[2]);
55+
data->m3_inv = derive_multiplier_inverse(data->secrets[2]);
5456
}
5557
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
5658

@@ -75,6 +77,7 @@ const HashSeed::Data* const HashSeed::kDefaultData = &kDefaultSeed;
7577
// Compile-time verification that m * m_inv === 1 for the derived secrets.
7678
static_assert(is_modular_inverse(kDefaultSeed.m1, kDefaultSeed.m1_inv));
7779
static_assert(is_modular_inverse(kDefaultSeed.m2, kDefaultSeed.m2_inv));
80+
static_assert(is_modular_inverse(kDefaultSeed.m3, kDefaultSeed.m3_inv));
7881
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
7982

8083
// static
@@ -102,6 +105,7 @@ void HashSeed::InitializeRoots(Isolate* isolate) {
102105
DeriveSecretsForArrayIndexHash(data);
103106
DCHECK(is_modular_inverse(data->m1, data->m1_inv));
104107
DCHECK(is_modular_inverse(data->m2, data->m2_inv));
108+
DCHECK(is_modular_inverse(data->m3, data->m3_inv));
105109
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
106110
#endif // V8_USE_DEFAULT_HASHER_SECRET
107111
}

‎deps/v8/src/numbers/hash-seed.h‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,8 @@ class V8_EXPORT_PRIVATE HashSeed {
5353
uint32_t m1_inv; // modular inverse of m1 mod 2^kArrayIndexValueBits
5454
uint32_t m2; // lower kArrayIndexValueBits bits of secret[1], must be odd
5555
uint32_t m2_inv; // modular inverse of m2 mod 2^kArrayIndexValueBits
56+
uint32_t m3; // lower kArrayIndexValueBits bits of secret[2], must be odd
57+
uint32_t m3_inv; // modular inverse of m3 mod 2^kArrayIndexValueBits
5658
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
5759
};
5860

@@ -65,11 +67,15 @@ class V8_EXPORT_PRIVATE HashSeed {
6567
static constexpr int kDerivedM1InvOffset = offsetof(Data, m1_inv);
6668
static constexpr int kDerivedM2Offset = offsetof(Data, m2);
6769
static constexpr int kDerivedM2InvOffset = offsetof(Data, m2_inv);
70+
static constexpr int kDerivedM3Offset = offsetof(Data, m3);
71+
static constexpr int kDerivedM3InvOffset = offsetof(Data, m3_inv);
6872

6973
inline uint32_t m1() const;
7074
inline uint32_t m1_inv() const;
7175
inline uint32_t m2() const;
7276
inline uint32_t m2_inv() const;
77+
inline uint32_t m3() const;
78+
inline uint32_t m3_inv() const;
7379
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
7480

7581
// Generates a hash seed (from --hash-seed or the RNG) and writes it

‎deps/v8/src/strings/string-hasher-inl.h‎

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -74,28 +74,34 @@ uint32_t StringHasher::SeedArrayIndexValue(uint32_t value,
7474
const HashSeed seed) {
7575
uint32_t m1 = seed.m1();
7676
uint32_t m2 = seed.m2();
77+
uint32_t m3 = seed.m3();
7778
constexpr uint32_t kShift = Name::kArrayIndexHashShift;
7879
constexpr uint32_t kMask = Name::kArrayIndexValueMask;
79-
// 2-round xorshift-multiply.
80+
// 3-round xorshift-multiply.
8081
uint32_t x = value;
8182
x ^= x >> kShift;
8283
x = (x * m1) & kMask;
8384
x ^= x >> kShift;
8485
x = (x * m2) & kMask;
8586
x ^= x >> kShift;
87+
x = (x * m3) & kMask;
88+
x ^= x >> kShift;
8689
return x;
8790
}
8891

8992
uint32_t StringHasher::UnseedArrayIndexValue(uint32_t value,
9093
const HashSeed seed) {
9194
uint32_t m1_inv = seed.m1_inv();
9295
uint32_t m2_inv = seed.m2_inv();
96+
uint32_t m3_inv = seed.m3_inv();
9397
uint32_t x = value;
9498
constexpr uint32_t kShift = Name::kArrayIndexHashShift;
9599
constexpr uint32_t kMask = Name::kArrayIndexValueMask;
96-
// 2-round xorshift-multiply.
100+
// 3-round xorshift-multiply (inverse).
97101
// Xorshift is an involution when kShift is at least half of the value width.
98102
x ^= x >> kShift;
103+
x = (x * m3_inv) & kMask;
104+
x ^= x >> kShift;
99105
x = (x * m2_inv) & kMask;
100106
x ^= x >> kShift;
101107
x = (x * m1_inv) & kMask;

‎deps/v8/src/strings/string-hasher.h‎

Lines changed: 9 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -63,22 +63,24 @@ class V8_EXPORT_PRIVATE StringHasher final {
6363

6464
#ifdef V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
6565
// When V8_ENABLE_SEEDED_ARRAY_INDEX_HASH is enabled, the numeric value
66-
// will be scrambled with 2 rounds of xorshift-multiply.
66+
// will be scrambled with 3 rounds of xorshift-multiply.
6767
//
6868
// x ^= x >> kShift; x = (x * m1) & kMask; // round 1
6969
// x ^= x >> kShift; x = (x * m2) & kMask; // round 2
70+
// x ^= x >> kShift; x = (x * m3) & kMask; // round 3
7071
// x ^= x >> kShift; // finalize
7172
//
72-
// To decode, apply the same steps with the modular inverses of m1 and m2 in
73-
// reverse order.
73+
// To decode, apply the same steps with the modular inverses of m1, m2
74+
// and m3 in reverse order.
7475
//
75-
// x ^= x >> kShift; x = (x * m2_inv) & kMask; // round 1
76-
// x ^= x >> kShift; x = (x * m1_inv) & kMask; // round 2
76+
// x ^= x >> kShift; x = (x * m3_inv) & kMask; // round 1
77+
// x ^= x >> kShift; x = (x * m2_inv) & kMask; // round 2
78+
// x ^= x >> kShift; x = (x * m1_inv) & kMask; // round 3
7779
// x ^= x >> kShift; // finalize
7880
//
7981
// where kShift = kArrayIndexValueBits / 2, kMask = kArrayIndexValueMask,
80-
// m1, m2 (both odd) are derived from the Isolate's rapidhash secrets.
81-
// m1_inv, m2_inv (modular inverses) are precomputed so that
82+
// m1, m2, m3 (all odd) are derived from the Isolate's rapidhash secrets.
83+
// m1_inv, m2_inv, m3_inv (modular inverses) are precomputed so that
8284
// UnseedArrayIndexValue can quickly recover the original value.
8385
static V8_INLINE uint32_t SeedArrayIndexValue(uint32_t value,
8486
const HashSeed seed);

0 commit comments

Comments
 (0)