1 // Copyright 2022 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #if !V8_ENABLE_WEBASSEMBLY 6 #error This header should only be included if WebAssembly is enabled. 7 #endif // !V8_ENABLE_WEBASSEMBLY 8 9 #ifndef V8_WASM_CANONICAL_TYPES_H_ 10 #define V8_WASM_CANONICAL_TYPES_H_ 11 12 #include <unordered_map> 13 14 #include "src/base/lazy-instance.h" 15 #include "src/wasm/wasm-module.h" 16 17 namespace v8 { 18 namespace internal { 19 namespace wasm { 20 21 // A singleton class, responsible for isorecursive canonicalization of wasm 22 // types. 23 // A recursive group is a subsequence of types explicitly marked in the type 24 // section of a wasm module. Identical recursive groups have to be canonicalized 25 // to a single canonical group and are are considered identical. Respective 26 // types in two identical groups are considered identical for all purposes. 27 // Two groups are considered identical if they have the same shape, and all 28 // type indices referenced in the same position in both groups reference: 29 // - identical types, if those do not belong to the rec. group, 30 // - types in the same relative position in the group, if those belong to the 31 // rec. group. 32 class TypeCanonicalizer { 33 public: 34 TypeCanonicalizer() = default; 35 36 // Singleton class; no copying or moving allowed. 37 TypeCanonicalizer(const TypeCanonicalizer& other) = delete; 38 TypeCanonicalizer& operator=(const TypeCanonicalizer& other) = delete; 39 TypeCanonicalizer(TypeCanonicalizer&& other) = delete; 40 TypeCanonicalizer& operator=(TypeCanonicalizer&& other) = delete; 41 42 // Registers the last {size} types of {module} as a recursive group, and 43 // possibly canonicalizes it if an identical one has been found. 44 // Modifies {module->isorecursive_canonical_type_ids}. 45 V8_EXPORT_PRIVATE void AddRecursiveGroup(WasmModule* module, uint32_t size); 46 47 // Returns if the type at {sub_index} in {sub_module} is a subtype of the 48 // type at {super_index} in {super_module} after canonicalization. 49 V8_EXPORT_PRIVATE bool IsCanonicalSubtype(uint32_t sub_index, 50 uint32_t super_index, 51 const WasmModule* sub_module, 52 const WasmModule* super_module); 53 54 private: 55 using TypeInModule = std::pair<const WasmModule*, uint32_t>; 56 struct CanonicalType { 57 TypeDefinition type_def; 58 bool is_relative_supertype; 59 60 bool operator==(const CanonicalType& other) const { 61 return type_def == other.type_def && 62 is_relative_supertype == other.is_relative_supertype; 63 } 64 65 bool operator!=(const CanonicalType& other) const { 66 return type_def != other.type_def || 67 is_relative_supertype != other.is_relative_supertype; 68 } 69 hash_valueCanonicalType70 size_t hash_value() const { 71 return base::hash_combine(type_def.kind, 72 base::hash_value(is_relative_supertype)); 73 } 74 }; 75 struct CanonicalGroup { 76 struct hash { operatorCanonicalGroup::hash77 size_t operator()(const CanonicalGroup& group) const { 78 return group.hash_value(); 79 } 80 }; 81 82 bool operator==(const CanonicalGroup& other) const { 83 return types == other.types; 84 } 85 86 bool operator!=(const CanonicalGroup& other) const { 87 return types != other.types; 88 } 89 hash_valueCanonicalGroup90 size_t hash_value() const { 91 size_t result = 0; 92 for (const CanonicalType& type : types) { 93 result = base::hash_combine(result, type.hash_value()); 94 } 95 return result; 96 } 97 98 std::vector<CanonicalType> types; 99 }; 100 101 int FindCanonicalGroup(CanonicalGroup&) const; 102 103 CanonicalType CanonicalizeTypeDef(const WasmModule* module, 104 TypeDefinition type, 105 uint32_t recursive_group_start); 106 ValueType CanonicalizeValueType(const WasmModule* module, ValueType type, 107 uint32_t recursive_group_start) const; 108 109 std::vector<uint32_t> canonical_supertypes_; 110 // group -> canonical id of first type 111 std::unordered_map<CanonicalGroup, uint32_t, CanonicalGroup::hash> 112 canonical_groups_; 113 AccountingAllocator allocator_; 114 Zone zone_{&allocator_, "canonical type zone"}; 115 base::Mutex mutex_; 116 }; 117 118 // Returns a reference to the TypeCanonicalizer shared by the entire process. 119 V8_EXPORT_PRIVATE TypeCanonicalizer* GetTypeCanonicalizer(); 120 121 } // namespace wasm 122 } // namespace internal 123 } // namespace v8 124 125 #endif // V8_WASM_CANONICAL_TYPES_H_ 126