Skip to content

Commit 20d9a7f

Browse files
backesV8 LUCI CQ
backes
authored and
V8 LUCI CQ
committed
[wasm] Remove relative type indexes from canonical types
Those relative types were leaking from the type canonicalizer, which leads to type confusion in callers. This CL fully removes the concept of relative type indexes (and thus removes the `CanonicalRelativeField` bit from the bitfield in `ValueTypeBase`). During canonicalization we pass the start and end of the recursion group into hashing and equality checking, and use this to compute relative indexes within the recursion group on demand. The stored version will always have absolute indexes though. [email protected] Bug: 379612177 Change-Id: I24154785c38dd3d8abb3d252bef4752024bad223 Fixed: 379009132 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/6035175 Reviewed-by: Jakob Kummerow <[email protected]> Commit-Queue: Clemens Backes <[email protected]> Cr-Commit-Position: refs/heads/main@{#97279}
1 parent c000741 commit 20d9a7f

File tree

8 files changed

+306
-199
lines changed

8 files changed

+306
-199
lines changed

‎src/base/bounds.h‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -14,9 +14,11 @@ namespace base {
1414
// Checks if value is in range [lower_limit, higher_limit] using a single
1515
// branch.
1616
template <typename T, typename U>
17+
requires((std::is_integral_v<T> || std::is_enum_v<T>) &&
18+
(std::is_integral_v<U> || std::is_enum_v<U>)) &&
19+
(sizeof(U) <= sizeof(T))
1720
inline constexpr bool IsInRange(T value, U lower_limit, U higher_limit) {
1821
DCHECK_LE(lower_limit, higher_limit);
19-
static_assert(sizeof(U) <= sizeof(T));
2022
using unsigned_T = typename std::make_unsigned<T>::type;
2123
// Use static_cast to support enum classes.
2224
return static_cast<unsigned_T>(static_cast<unsigned_T>(value) -
@@ -27,10 +29,12 @@ inline constexpr bool IsInRange(T value, U lower_limit, U higher_limit) {
2729

2830
// Like IsInRange but for the half-open range [lower_limit, higher_limit).
2931
template <typename T, typename U>
32+
requires((std::is_integral_v<T> || std::is_enum_v<T>) &&
33+
(std::is_integral_v<U> || std::is_enum_v<U>)) &&
34+
(sizeof(U) <= sizeof(T))
3035
inline constexpr bool IsInHalfOpenRange(T value, U lower_limit,
3136
U higher_limit) {
3237
DCHECK_LE(lower_limit, higher_limit);
33-
static_assert(sizeof(U) <= sizeof(T));
3438
using unsigned_T = typename std::make_unsigned<T>::type;
3539
// Use static_cast to support enum classes.
3640
return static_cast<unsigned_T>(static_cast<unsigned_T>(value) -

‎src/wasm/canonical-types.cc‎

Lines changed: 91 additions & 95 deletions
Large diffs are not rendered by default.

‎src/wasm/canonical-types.h‎

Lines changed: 184 additions & 68 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@
1111

1212
#include <unordered_map>
1313

14+
#include "src/base/bounds.h"
1415
#include "src/base/functional.h"
1516
#include "src/wasm/value-type.h"
1617
#include "src/wasm/wasm-module.h"
@@ -144,137 +145,252 @@ class TypeCanonicalizer {
144145
bool is_final = false;
145146
bool is_shared = false;
146147
uint8_t subtyping_depth = 0;
147-
bool is_relative_supertype;
148148

149149
constexpr CanonicalType(const CanonicalSig* sig,
150150
CanonicalTypeIndex supertype, bool is_final,
151-
bool is_shared, bool is_relative_supertype)
151+
bool is_shared)
152152
: function_sig(sig),
153153
supertype(supertype),
154154
kind(kFunction),
155155
is_final(is_final),
156-
is_shared(is_shared),
157-
is_relative_supertype(is_relative_supertype) {}
156+
is_shared(is_shared) {}
158157

159158
constexpr CanonicalType(const CanonicalStructType* type,
160159
CanonicalTypeIndex supertype, bool is_final,
161-
bool is_shared, bool is_relative_supertype)
160+
bool is_shared)
162161
: struct_type(type),
163162
supertype(supertype),
164163
kind(kStruct),
165164
is_final(is_final),
166-
is_shared(is_shared),
167-
is_relative_supertype(is_relative_supertype) {}
165+
is_shared(is_shared) {}
168166

169167
constexpr CanonicalType(const CanonicalArrayType* type,
170168
CanonicalTypeIndex supertype, bool is_final,
171-
bool is_shared, bool is_relative_supertype)
169+
bool is_shared)
172170
: array_type(type),
173171
supertype(supertype),
174172
kind(kArray),
175173
is_final(is_final),
176-
is_shared(is_shared),
177-
is_relative_supertype(is_relative_supertype) {}
174+
is_shared(is_shared) {}
178175

179176
constexpr CanonicalType() = default;
177+
};
178+
179+
// Define the range of a recursion group; for use in {CanonicalHashing} and
180+
// {CanonicalEquality}.
181+
struct RecursionGroupRange {
182+
const CanonicalTypeIndex start;
183+
const CanonicalTypeIndex end;
180184

181-
bool operator==(const CanonicalType& other) const {
182-
if (supertype != other.supertype) return false;
183-
if (kind != other.kind) return false;
184-
if (is_final != other.is_final) return false;
185-
if (is_shared != other.is_shared) return false;
186-
if (is_relative_supertype != other.is_relative_supertype) return false;
187-
if (kind == kFunction) return *function_sig == *other.function_sig;
188-
if (kind == kStruct) return *struct_type == *other.struct_type;
189-
DCHECK_EQ(kArray, kind);
190-
return *array_type == *other.array_type;
185+
bool Contains(CanonicalTypeIndex index) const {
186+
return base::IsInRange(index.index, start.index, end.index);
191187
}
192188

193-
bool operator!=(const CanonicalType& other) const {
194-
return !operator==(other);
189+
CanonicalTypeIndex RelativeIndex(CanonicalTypeIndex index) const {
190+
return Contains(index)
191+
// Make the value_type relative within the recursion group.
192+
? CanonicalTypeIndex{index.index - start.index}
193+
: index;
195194
}
196195

197-
size_t hash_value() const {
198-
uint32_t metadata = (supertype.index << 2) | (is_final ? 2 : 0) |
199-
(is_relative_supertype ? 1 : 0);
200-
base::Hasher hasher;
196+
CanonicalValueType RelativeType(CanonicalValueType type) const {
197+
return type.has_index()
198+
? CanonicalValueType::FromIndex(
199+
type.kind(), RelativeIndex(type.ref_index()))
200+
: type;
201+
}
202+
};
203+
204+
// Support for hashing of recursion groups, where type indexes have to be
205+
// hashed relative to the recursion group.
206+
struct CanonicalHashing {
207+
base::Hasher hasher;
208+
const RecursionGroupRange recgroup;
209+
210+
explicit CanonicalHashing(RecursionGroupRange recgroup)
211+
: recgroup{recgroup} {}
212+
213+
void Add(CanonicalType type) {
214+
CanonicalTypeIndex relative_supertype =
215+
recgroup.RelativeIndex(type.supertype);
216+
uint32_t metadata =
217+
(relative_supertype.index << 1) | (type.is_final ? 1 : 0);
201218
hasher.Add(metadata);
202-
if (kind == kFunction) {
203-
hasher.Add(*function_sig);
204-
} else if (kind == kStruct) {
205-
hasher.Add(*struct_type);
206-
} else {
207-
DCHECK_EQ(kArray, kind);
208-
hasher.Add(*array_type);
219+
switch (type.kind) {
220+
case CanonicalType::kFunction:
221+
Add(*type.function_sig);
222+
break;
223+
case CanonicalType::kStruct:
224+
Add(*type.struct_type);
225+
break;
226+
case CanonicalType::kArray:
227+
Add(*type.array_type);
228+
break;
209229
}
210-
return hasher.hash();
211230
}
231+
232+
void Add(CanonicalValueType value_type) {
233+
hasher.Add(recgroup.RelativeType(value_type));
234+
}
235+
236+
void Add(const CanonicalSig& sig) {
237+
hasher.Add(sig.parameter_count());
238+
for (CanonicalValueType type : sig.all()) Add(type);
239+
}
240+
241+
void Add(const CanonicalStructType& struct_type) {
242+
hasher.AddRange(struct_type.mutabilities());
243+
for (const ValueTypeBase& field : struct_type.fields()) {
244+
Add(CanonicalValueType{field});
245+
}
246+
}
247+
248+
void Add(const CanonicalArrayType& array_type) {
249+
hasher.Add(array_type.mutability());
250+
Add(array_type.element_type());
251+
}
252+
253+
size_t hash() const { return hasher.hash(); }
212254
};
213-
struct CanonicalGroup {
214-
CanonicalGroup(Zone* zone, size_t size)
215-
: types(zone->AllocateVector<CanonicalType>(size)) {}
216255

217-
bool operator==(const CanonicalGroup& other) const {
218-
return types == other.types;
256+
// Support for equality checking of recursion groups, where type indexes have
257+
// to be compared relative to their respective recursion group.
258+
struct CanonicalEquality {
259+
// Recursion group bounds for LHS and RHS.
260+
const RecursionGroupRange recgroup1;
261+
const RecursionGroupRange recgroup2;
262+
263+
CanonicalEquality(RecursionGroupRange recgroup1,
264+
RecursionGroupRange recgroup2)
265+
: recgroup1{recgroup1}, recgroup2{recgroup2} {}
266+
267+
bool EqualType(const CanonicalType& type1,
268+
const CanonicalType& type2) const {
269+
if (recgroup1.RelativeIndex(type1.supertype) !=
270+
recgroup2.RelativeIndex(type2.supertype)) {
271+
return false;
272+
}
273+
if (type1.is_final != type2.is_final) return false;
274+
if (type1.is_shared != type2.is_shared) return false;
275+
switch (type1.kind) {
276+
case CanonicalType::kFunction:
277+
return type2.kind == CanonicalType::kFunction &&
278+
EqualSig(*type1.function_sig, *type2.function_sig);
279+
case CanonicalType::kStruct:
280+
return type2.kind == CanonicalType::kStruct &&
281+
EqualStructType(*type1.struct_type, *type2.struct_type);
282+
case CanonicalType::kArray:
283+
return type2.kind == CanonicalType::kArray &&
284+
EqualArrayType(*type1.array_type, *type2.array_type);
285+
}
219286
}
220287

221-
bool operator!=(const CanonicalGroup& other) const {
222-
return types != other.types;
288+
bool EqualTypes(base::Vector<const CanonicalType> types1,
289+
base::Vector<const CanonicalType> types2) const {
290+
return std::equal(types1.begin(), types1.end(), types2.begin(),
291+
types2.end(),
292+
std::bind_front(&CanonicalEquality::EqualType, this));
293+
}
294+
295+
bool EqualValueType(CanonicalValueType type1,
296+
CanonicalValueType type2) const {
297+
return recgroup1.RelativeType(type1) == recgroup2.RelativeType(type2);
298+
}
299+
300+
bool EqualSig(const CanonicalSig& sig1, const CanonicalSig& sig2) const {
301+
if (sig1.parameter_count() != sig2.parameter_count()) return false;
302+
return std::equal(
303+
sig1.all().begin(), sig1.all().end(), sig2.all().begin(),
304+
sig2.all().end(),
305+
std::bind_front(&CanonicalEquality::EqualValueType, this));
306+
}
307+
308+
bool EqualStructType(const CanonicalStructType& type1,
309+
const CanonicalStructType& type2) const {
310+
return std::equal(
311+
type1.fields().begin(), type1.fields().end(), type2.fields().begin(),
312+
type2.fields().end(),
313+
std::bind_front(&CanonicalEquality::EqualValueType, this));
314+
}
315+
316+
bool EqualArrayType(const CanonicalArrayType& type1,
317+
const CanonicalArrayType& type2) const {
318+
return type1.mutability() == type2.mutability() &&
319+
EqualValueType(type1.element_type(), type2.element_type());
320+
}
321+
};
322+
323+
struct CanonicalGroup {
324+
CanonicalGroup(Zone* zone, size_t size, CanonicalTypeIndex start)
325+
: types(zone->AllocateVector<CanonicalType>(size)), start(start) {
326+
// size >= 2; otherwise a `CanonicalSingletonGroup` should have been used.
327+
DCHECK_LE(2, size);
328+
}
329+
330+
bool operator==(const CanonicalGroup& other) const {
331+
CanonicalTypeIndex end{start.index +
332+
static_cast<uint32_t>(types.size() - 1)};
333+
CanonicalTypeIndex other_end{
334+
other.start.index + static_cast<uint32_t>(other.types.size() - 1)};
335+
CanonicalEquality equality{{start, end}, {other.start, other_end}};
336+
return equality.EqualTypes(types, other.types);
223337
}
224338

225339
size_t hash_value() const {
226-
return base::Hasher{}.AddRange(types.begin(), types.end()).hash();
340+
CanonicalTypeIndex end{start.index + static_cast<uint32_t>(types.size()) -
341+
1};
342+
CanonicalHashing hasher{{start, end}};
343+
for (CanonicalType t : types) {
344+
hasher.Add(t);
345+
}
346+
return hasher.hash();
227347
}
228348

229349
// The storage of this vector is the TypeCanonicalizer's zone_.
230-
base::Vector<CanonicalType> types;
350+
const base::Vector<CanonicalType> types;
351+
const CanonicalTypeIndex start;
231352
};
232353

233354
struct CanonicalSingletonGroup {
234-
struct hash {
235-
size_t operator()(const CanonicalSingletonGroup& group) const {
236-
return group.hash_value();
237-
}
238-
};
239-
240355
bool operator==(const CanonicalSingletonGroup& other) const {
241-
return type == other.type;
356+
CanonicalEquality equality{{index, index}, {other.index, other.index}};
357+
return equality.EqualType(type, other.type);
242358
}
243359

244-
size_t hash_value() const { return type.hash_value(); }
360+
size_t hash_value() const {
361+
CanonicalHashing hasher{{index, index}};
362+
hasher.Add(type);
363+
return hasher.hash();
364+
}
245365

246366
CanonicalType type;
367+
CanonicalTypeIndex index;
247368
};
248369

249370
void AddPredefinedArrayTypes();
250371

251372
CanonicalTypeIndex FindCanonicalGroup(const CanonicalGroup&) const;
252373
CanonicalTypeIndex FindCanonicalGroup(const CanonicalSingletonGroup&) const;
253374

254-
// Canonicalize all types present in {type} (including supertype) according to
255-
// {CanonicalizeValueType}.
256-
CanonicalType CanonicalizeTypeDef(const WasmModule* module,
257-
TypeDefinition type,
258-
uint32_t recursive_group_start);
259-
260-
// An indexed type gets mapped to a {CanonicalValueType::WithRelativeIndex}
261-
// if its index points inside the new canonical group; otherwise, the index
262-
// gets mapped to its canonical representative.
263-
CanonicalValueType CanonicalizeValueType(
264-
const WasmModule* module, ValueType type,
265-
uint32_t recursive_group_start) const;
375+
// Canonicalize the module-specific type at `module_type_idx` within the
376+
// recursion group starting at `recursion_group_start`, using
377+
// `canonical_recgroup_start` as the start offset of types within the
378+
// recursion group.
379+
CanonicalType CanonicalizeTypeDef(
380+
const WasmModule* module, ModuleTypeIndex module_type_idx,
381+
ModuleTypeIndex recgroup_start,
382+
CanonicalTypeIndex canonical_recgroup_start);
266383

267384
CanonicalTypeIndex AddRecursiveGroup(CanonicalType type);
268385

269386
void CheckMaxCanonicalIndex() const;
270387

271388
std::vector<CanonicalTypeIndex> canonical_supertypes_;
272-
// Maps groups of size >=2 to the canonical id of the first type.
273-
std::unordered_map<CanonicalGroup, CanonicalTypeIndex,
274-
base::hash<CanonicalGroup>>
389+
// Set of all known canonical recgroups of size >=2.
390+
std::unordered_set<CanonicalGroup, base::hash<CanonicalGroup>>
275391
canonical_groups_;
276-
// Maps group of size 1 to the canonical id of the type.
277-
std::unordered_map<CanonicalSingletonGroup, CanonicalTypeIndex,
392+
// Set of all known canonical recgroups of size 1.
393+
std::unordered_set<CanonicalSingletonGroup,
278394
base::hash<CanonicalSingletonGroup>>
279395
canonical_singleton_groups_;
280396
// Maps canonical indices back to the function signature.

‎src/wasm/std-object-sizes.h‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -45,8 +45,8 @@ inline size_t ContentSize(const std::unordered_map<Key, T, Hash>& map) {
4545
return raw * 4 / 3;
4646
}
4747

48-
template <typename T>
49-
inline size_t ContentSize(std::unordered_set<T> set) {
48+
template <typename T, typename Hash>
49+
inline size_t ContentSize(const std::unordered_set<T, Hash>& set) {
5050
// Very rough lower bound approximation: two internal pointers per entry.
5151
size_t raw = set.size() * (sizeof(T) + 2 * sizeof(void*));
5252
// In the spirit of computing lower bounds of definitely-used memory,

‎src/wasm/struct-types.h‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -266,8 +266,9 @@ inline std::ostream& operator<<(std::ostream& out, StructTypeBase type) {
266266

267267
// Support base::hash<StructTypeBase>.
268268
inline size_t hash_value(const StructTypeBase& type) {
269+
// Note: If you update this you probably also want to update
270+
// `CanonicalHashing::Add(CanonicalStructType)`.
269271
return base::Hasher{}
270-
.Add(type.field_count())
271272
.AddRange(type.fields())
272273
.AddRange(type.mutabilities())
273274
.hash();
@@ -324,6 +325,8 @@ inline size_t hash_value(const ArrayType& type) {
324325
return base::Hasher::Combine(type.element_type(), type.mutability());
325326
}
326327
inline size_t hash_value(const CanonicalArrayType& type) {
328+
// Note: If you update this you probably also want to update
329+
// `CanonicalHashing::Add(CanonicalArrayType)`.
327330
return base::Hasher::Combine(type.element_type(), type.mutability());
328331
}
329332

0 commit comments

Comments
 (0)