From 20d9a7f760c018183c836283017a321638b66810 Mon Sep 17 00:00:00 2001
From: Clemens Backes <clemensb@chromium.org>
Date: Tue, 19 Nov 2024 18:17:33 +0100
Subject: [PATCH] [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.

R=jkummerow@chromium.org

Bug: 379612177
Change-Id: I24154785c38dd3d8abb3d252bef4752024bad223
Fixed: 379009132
Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/6035175
Reviewed-by: Jakob Kummerow <jkummerow@chromium.org>
Commit-Queue: Clemens Backes <clemensb@chromium.org>
Cr-Commit-Position: refs/heads/main@{#97279}
---

diff --git a/src/base/bounds.h b/src/base/bounds.h
index 85f7bba..1646e81 100644
--- a/src/base/bounds.h
+++ b/src/base/bounds.h
@@ -14,9 +14,11 @@
 // Checks if value is in range [lower_limit, higher_limit] using a single
 // branch.
 template <typename T, typename U>
+  requires((std::is_integral_v<T> || std::is_enum_v<T>) &&
+           (std::is_integral_v<U> || std::is_enum_v<U>)) &&
+          (sizeof(U) <= sizeof(T))
 inline constexpr bool IsInRange(T value, U lower_limit, U higher_limit) {
   DCHECK_LE(lower_limit, higher_limit);
-  static_assert(sizeof(U) <= sizeof(T));
   using unsigned_T = typename std::make_unsigned<T>::type;
   // Use static_cast to support enum classes.
   return static_cast<unsigned_T>(static_cast<unsigned_T>(value) -
@@ -27,10 +29,12 @@
 
 // Like IsInRange but for the half-open range [lower_limit, higher_limit).
 template <typename T, typename U>
+  requires((std::is_integral_v<T> || std::is_enum_v<T>) &&
+           (std::is_integral_v<U> || std::is_enum_v<U>)) &&
+          (sizeof(U) <= sizeof(T))
 inline constexpr bool IsInHalfOpenRange(T value, U lower_limit,
                                         U higher_limit) {
   DCHECK_LE(lower_limit, higher_limit);
-  static_assert(sizeof(U) <= sizeof(T));
   using unsigned_T = typename std::make_unsigned<T>::type;
   // Use static_cast to support enum classes.
   return static_cast<unsigned_T>(static_cast<unsigned_T>(value) -
diff --git a/src/wasm/canonical-types.cc b/src/wasm/canonical-types.cc
index 3443018..2ecb78b 100644
--- a/src/wasm/canonical-types.cc
+++ b/src/wasm/canonical-types.cc
@@ -43,11 +43,17 @@
   // Multiple threads could try to register recursive groups concurrently.
   // TODO(manoskouk): Investigate if we can fine-grain the synchronization.
   base::MutexGuard mutex_guard(&mutex_);
+  // Compute the first canonical index in the recgroup in the case that it does
+  // not already exist.
+  CanonicalTypeIndex first_new_canonical_index{
+      static_cast<uint32_t>(canonical_supertypes_.size())};
+
   DCHECK_GE(module->types.size(), start_index + size);
-  CanonicalGroup group{&zone_, size};
+  CanonicalGroup group{&zone_, size, first_new_canonical_index};
   for (uint32_t i = 0; i < size; i++) {
-    group.types[i] = CanonicalizeTypeDef(module, module->types[start_index + i],
-                                         start_index);
+    group.types[i] = CanonicalizeTypeDef(
+        module, ModuleTypeIndex{start_index + i}, ModuleTypeIndex{start_index},
+        first_new_canonical_index);
   }
   if (CanonicalTypeIndex canonical_index = FindCanonicalGroup(group);
       canonical_index.valid()) {
@@ -62,22 +68,13 @@
     // allocated in {CanonicalizeTypeDef{).
     return;
   }
-  // Identical group not found. Add new canonical representatives for the new
-  // types.
-  uint32_t first_canonical_index =
-      static_cast<uint32_t>(canonical_supertypes_.size());
-  canonical_supertypes_.resize(first_canonical_index + size);
+  canonical_supertypes_.resize(first_new_canonical_index.index + size);
   CheckMaxCanonicalIndex();
   for (uint32_t i = 0; i < size; i++) {
     CanonicalType& canonical_type = group.types[i];
-    // Compute the canonical index of the supertype: If it is relative, we
-    // need to add {first_canonical_index}.
-    canonical_supertypes_[first_canonical_index + i] =
-        canonical_type.is_relative_supertype
-            ? CanonicalTypeIndex{canonical_type.supertype.index +
-                                 first_canonical_index}
-            : canonical_type.supertype;
-    CanonicalTypeIndex canonical_id{first_canonical_index + i};
+    canonical_supertypes_[first_new_canonical_index.index + i] =
+        canonical_type.supertype;
+    CanonicalTypeIndex canonical_id{first_new_canonical_index.index + i};
     module->isorecursive_canonical_type_ids[start_index + i] = canonical_id;
     if (canonical_type.kind == CanonicalType::kFunction) {
       const CanonicalSig* sig = canonical_type.function_sig;
@@ -85,15 +82,13 @@
     }
   }
   // Check that this canonical ID is not used yet.
-  DCHECK(std::none_of(canonical_singleton_groups_.begin(),
-                      canonical_singleton_groups_.end(), [=](auto& entry) {
-                        return entry.second.index == first_canonical_index;
-                      }));
-  DCHECK(std::none_of(canonical_groups_.begin(), canonical_groups_.end(),
-                      [=](auto& entry) {
-                        return entry.second.index == first_canonical_index;
-                      }));
-  canonical_groups_.emplace(group, CanonicalTypeIndex{first_canonical_index});
+  DCHECK(std::none_of(
+      canonical_singleton_groups_.begin(), canonical_singleton_groups_.end(),
+      [=](auto& entry) { return entry.index == first_new_canonical_index; }));
+  DCHECK(std::none_of(
+      canonical_groups_.begin(), canonical_groups_.end(),
+      [=](auto& entry) { return entry.start == first_new_canonical_index; }));
+  canonical_groups_.emplace(group);
 }
 
 void TypeCanonicalizer::AddRecursiveSingletonGroup(WasmModule* module) {
@@ -105,8 +100,11 @@
                                                    uint32_t start_index) {
   base::MutexGuard guard(&mutex_);
   DCHECK_GT(module->types.size(), start_index);
-  CanonicalTypeIndex canonical_index = AddRecursiveGroup(
-      CanonicalizeTypeDef(module, module->types[start_index], start_index));
+  CanonicalTypeIndex first_new_canonical_index{
+      static_cast<uint32_t>(canonical_supertypes_.size())};
+  CanonicalTypeIndex canonical_index = AddRecursiveGroup(CanonicalizeTypeDef(
+      module, ModuleTypeIndex{start_index}, ModuleTypeIndex{start_index},
+      first_new_canonical_index));
   module->isorecursive_canonical_type_ids[start_index] = canonical_index;
 }
 
@@ -118,7 +116,6 @@
 #endif
   const bool kFinal = true;
   const bool kNotShared = false;
-  const bool kNonRelativeSupertype = false;
   // Because of the checks above, we can treat the type_def as canonical.
   // TODO(366180605): It would be nice to not have to rely on a cast here.
   // Is there a way to avoid it? In the meantime, these asserts provide at
@@ -127,13 +124,14 @@
   static_assert(CanonicalValueType::Primitive(kI32).raw_bit_field() ==
                 ValueType::Primitive(kI32).raw_bit_field());
   CanonicalType canonical{reinterpret_cast<const CanonicalSig*>(sig),
-                          CanonicalTypeIndex{kNoSuperType}, kFinal, kNotShared,
-                          kNonRelativeSupertype};
+                          CanonicalTypeIndex{kNoSuperType}, kFinal, kNotShared};
   base::MutexGuard guard(&mutex_);
   // Fast path lookup before canonicalizing (== copying into the
   // TypeCanonicalizer's zone) the function signature.
-  CanonicalTypeIndex index =
-      FindCanonicalGroup(CanonicalSingletonGroup{canonical});
+  CanonicalTypeIndex hypothetical_new_canonical_index{
+      static_cast<uint32_t>(canonical_supertypes_.size())};
+  CanonicalTypeIndex index = FindCanonicalGroup(
+      CanonicalSingletonGroup{canonical, hypothetical_new_canonical_index});
   if (index.valid()) return index;
   // Copy into this class's zone, then call the generic {AddRecursiveGroup}.
   CanonicalSig::Builder builder(&zone_, sig->return_count(),
@@ -145,12 +143,16 @@
     builder.AddParam(CanonicalValueType{param});
   }
   canonical.function_sig = builder.Get();
-  return AddRecursiveGroup(canonical);
+  CanonicalTypeIndex canonical_index = AddRecursiveGroup(canonical);
+  DCHECK_EQ(canonical_index, hypothetical_new_canonical_index);
+  return canonical_index;
 }
 
 CanonicalTypeIndex TypeCanonicalizer::AddRecursiveGroup(CanonicalType type) {
   mutex_.AssertHeld();  // The caller must hold the mutex.
-  CanonicalSingletonGroup group{type};
+  CanonicalTypeIndex new_canonical_index{
+      static_cast<uint32_t>(canonical_supertypes_.size())};
+  CanonicalSingletonGroup group{type, new_canonical_index};
   if (CanonicalTypeIndex index = FindCanonicalGroup(group); index.valid()) {
     //  Make sure this signature can be looked up later.
     DCHECK_IMPLIES(type.kind == CanonicalType::kFunction,
@@ -158,26 +160,21 @@
     return index;
   }
   static_assert(kMaxCanonicalTypes <= kMaxUInt32);
-  CanonicalTypeIndex index{static_cast<uint32_t>(canonical_supertypes_.size())};
   // Check that this canonical ID is not used yet.
-  DCHECK(std::none_of(canonical_singleton_groups_.begin(),
-                      canonical_singleton_groups_.end(),

diff --git a/test/unittests/wasm/subtyping-unittest.cc b/test/unittests/wasm/subtyping-unittest.cc
index 4d02be7..33a8649 100644
--- a/test/unittests/wasm/subtyping-unittest.cc
+++ b/test/unittests/wasm/subtyping-unittest.cc
@@ -74,9 +74,15 @@
 
   // Set up two identical modules.
   for (WasmModule* module : {module1, module2}) {
-    /*  0 */ DefineStruct(module, {mut(ref(2)), immut(refNull(2))});
-    /*  1 */ DefineStruct(module, {mut(ref(2)), immut(ref(2))}, Idx{0});
-    /*  2 */ DefineArray(module, immut(ref(0)));
+    // Three mutually recursive types.
+    /*  0 */ DefineStruct(module, {mut(ref(2)), immut(refNull(2))},
+                          kNoSuperType, false, false, false);
+    /*  1 */ DefineStruct(module, {mut(ref(2)), immut(ref(2))}, Idx{0}, false,
+                          false, false);
+    /*  2 */ DefineArray(module, immut(ref(0)), kNoSuperType, false, false,
+                         false);
+    GetTypeCanonicalizer()->AddRecursiveGroup(module, 3);
+
     /*  3 */ DefineArray(module, immut(ref(1)), Idx{2});
     /*  4 */ DefineStruct(module, {mut(ref(2)), immut(ref(3)), immut(kWasmF64)},
                           Idx{1});